Educational Codeforces Round 108 (Rated for Div. 2) C. Berland Regional（思维，枚举）

Educational Codeforces Round 108 (Rated for Div. 2) C. Berland Regional（思维，枚举）

（之前写在小号里了，现在大号找回来了，所以再搬回来）

一、算法分析

基本思路就是枚举，还有利用vector的一些小技巧。注意的点是，最后的枚举方式要有一个小优化，不能外层对k进行枚举，如果那样会超时，因为两层循环都是n。而是应该开一个res数组，以组为单位去维护res数组。

二、代码及注释

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 #define LL long long 
 7 using namespace std;
 8 const int N=200050;
 9 vector s[N];
10 int n;
11 int u[N];
12 LL res[N];                                            //res of every group
13 int main(){
14     
15     int T;
16     cin>>T;
17     while(T--){
18         scanf("%d",&n);
19         for(int i=1;i<=n;i++){
20             scanf("%d",&u[i]);
21             s[i].clear();
22             res[i]=0;
23         }
24         for(int i=1;i<=n;i++){
25             int v;
26             scanf("%d",&v);
27             s[u[i]].push_back(v);
28         }
29         for(int i=1;i<=n;i++){
30             sort(s[i].begin(),s[i].end());
31             reverse(s[i].begin(),s[i].end());
32             for(int j=1;j					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/3970568.html