首页 > 代码库 > Codeforces 730A:Toda 2(multiset模拟)
Codeforces 730A:Toda 2(multiset模拟)
http://codeforces.com/problemset/problem/730/A
题意:有n个人打天梯,想让这n个人的分数相同,每场比赛必须有2-5个人参赛,参赛的人会降低一分,问一个合理方案让所有人的分数相同。
思路:不限制比赛场数,那么只用考虑2-3个人参赛的情况(因为4和5可以由2和3组成)。但是这个时候就不知道什么时候用3什么时候用2了。。
看别人代码。只有最大的三个数是一样的时候才用3,其他时候都用2。
然后很暴力地用multiset来模拟比赛。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define N 105 4 struct node { 5 int r, id; 6 friend bool operator < (const node &a, const node &b) { return a.r > b.r; } 7 }; 8 multiset<node> s; 9 vector<string> res;10 11 int main() {12 int n, r;13 scanf("%d", &n);14 for(int i = 1; i <= n; i++) 15 scanf("%d", &r), s.insert((node) {r, i});16 while(s.begin()->r != s.rbegin()->r) {17 vector<node> tmp; string ans;18 for(int i = 0; i < n; i++) ans += ‘0‘;19 int cnt = 2;20 if(s.count(*s.begin()) == 3) cnt = 3;21 for(int i = 0; i < cnt; i++) {22 node now = *s.begin(); s.erase(s.begin());23 ans[now.id-1] = ‘1‘;24 if(now.r > 0) now.r--; 25 tmp.push_back(now);26 }27 for(int i = 0; i < cnt; i++) s.insert(tmp[i]);28 res.push_back(ans);29 }30 printf("%d\n%d\n", s.begin()->r, res.size());31 for(int i = 0; i < res.size(); i++) cout << res[i] << endl;32 return 0;33 }
Codeforces 730A:Toda 2(multiset模拟)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。