codeforces 730 A Toda 2

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;}