Codeforces 1090C New Year Presents
发布时间:2020-12-16 09:12:38 所属栏目:百科 来源:网络整理
导读:New Year Presents 用set模拟一下。。 写的bug有点多。 #includebits/stdc++.h #define LL long long #define fi first #define se second #define mk make_pair #define PII pairint,int using namespace std; const int N = ( int )1e5 + 7 ; int n,m,sum,
New Year Presents 用set模拟一下。。 写的bug有点多。 #include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk make_pair #define PII pair<int,int> using namespace std; const int N = (int)1e5 + 7; int n,m,sum,min_cnt,tar[N],num[N],vis[N]; bool ban[N],gg[N]; vector<int> V[N],P[N],T[N]; set<int> S; vector<pair<PII,int>> ans; int main() { scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) { int s; scanf("%d",&s); num[i] = s; sum += s; while(s--) { int x; scanf("%d",&x); V[i].push_back(x); } } min_cnt = sum / n; int need = sum % n; for(int i = 1; i <= n && need; i++) { if(num[i] >= min_cnt + 1) { gg[i] = true; need--; } } for(int i = 1; i <= n; i++) { if(num[i] > min_cnt) { tar[i] = gg[i] ? min_cnt + 1 : min_cnt; if(num[i] > tar[i]) { for(auto &t : V[i]) { P[t].push_back(i); } } } else if(num[i] < min_cnt || need && num[i] == min_cnt) { if(need) tar[i] = min_cnt + 1,need--; else tar[i] = min_cnt; for(auto &t : V[i]) { T[t].push_back(i); } S.insert(i); } } for(int i = 1; i <= m; i++) { for(auto &id : T[i]) { vis[id] = i; } int pt = 0; while(pt < P[i].size() && ban[P[i][pt]]) pt++; vector<int> del; for(auto &id : S) { if(pt >= P[i].size()) break; if(vis[id] == i) continue; ans.push_back(mk(mk(P[i][pt],id),i)); num[P[i][pt]]--; if(num[P[i][pt]] == tar[P[i][pt]]) { ban[P[i][pt]] = true; } num[id]++; if(num[id] == tar[id]) { del.push_back(id); } pt++; while(pt < P[i].size() && ban[P[i][pt]]) pt++; } for(auto &id : del) S.erase(id); } printf("%dn",(int)ans.size()); for(auto &t : ans) { printf("%d %d %dn",t.fi.fi,t.fi.se,t.se); } return 0; } /* */ (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |