PRoblem

codeforces.com/problemset/problem/730/A

Reference

blog.csdn.net/ACMore_Xiong/article/details/52907334

題意

有 n 個正整數，每次可以選其中的 2 ~ 5 個數來同時減掉 1，減到 0 之后可以繼續減但值還是 0。

要使得它們最終全部相等，并且讓這個數盡量大。

Analysis

只考慮同時減2個或3個的情況（如果有多個相等的最大值，可以把它們分成兩個一組或三個一組，多減幾次）。

如果剛好有3個相等的最大值，就選中那3個一起減；否則，選最大的兩個一起減。直到最大值和最小值相等。

之前以為 multiset 的 rbegin() 和 end() 返回值是一樣的，一直 RE。

但其實 end() 返回的是最后一個元素的后一個位置，而 rbegin() 是最后一個元素的位置。

multiset 的 erase() 不能接受 rbegin() 的返回值（類型是 reverse_iterator），但能接受 begin() 的返回值，所以我是按降序排。

聽說 multiset 比較相等的時候不是用“==”，而是用“ ! (a < b) && ! (b < a) ”，所以不需要重載“==”，只要重載“<”。（用 count() 的時候）

（p.s.：原來“ ios::sync_with_stdio(false) ”這句是要寫在函數里面的…）

Source code

#include <iostream>#include <string>#include <vector>#include <set>using namespace std;const int N = 100;struct node{	int id, r;	node() {}	node(int _i, int _r): id(_i), r(_r) {}	bool Operator < (const node &nd) const	{		return r > nd.r;	}};multiset<node> ms;vector<string> ans;int main(){	ios::sync_with_stdio(false);	int n;	cin >> n;	for(int i=0, r; i<n; ++i)	{		cin >> r;		ms.insert(node(i, r));	}	for(int num=2; ms.begin()->r != ms.rbegin()->r; num=2)	{		if(ms.count(*ms.begin()) == 3)			++num;		vector<node> v(num);		string s(n, '0');		for(int i=0; i<num; ++i)		{			v[i] = *ms.begin();			ms.erase(ms.begin());			if(--v[i].r < 0)				v[i].r = 0;			s[v[i].id] = '1';		}		ans.push_back(s);		ms.insert(v.begin(), v.end());	}	cout << ms.begin()->r << '/n' << ans.size() << '/n';	for(int i=0, e=ans.size(); i<e; ++i)		cout << ans[i] << '/n';	ms.clear();	ans.clear();	return 0;}