3.29CF小结

Educational Codeforces Round 108 (Rated for Div. 2)

AB都是思维题目，我比较快的拿下来了

but我A题又双叒叕忘记看数据范围了，忘记开ll

导致我怀疑是不是我的推断错了，浪费了时间

$一定要看数据范围，不然就保险一点开ll$

$开了ll也不要忘记写lld$

讲讲C题

题意：

有n位同学，分别来自不同的学校，有不同的编程水平，每个学校可以派出n个队，求当每个队人数为k时，每个学校派出的队伍的编程水平总和。

计算方式:

题解

//先总结

我原本写了multiset，怎么可能不会T嘛，我把考虑的重点糊掉了

（还有multiset就无法在原数组上预处理了，抛弃抛弃

说到底是复杂度不会算，因为真正拉时间的是算答案tmp的时候，

我即使，排序了，每次减去，去遍历也会T

而且multiset的常数我不知道，每次insert之后都保证是有序的，那么每次排序（？）

怎么可能有vector插入完成最后排序一次快嘛

解法
贪心，如果某个学校要让某个人不去的话，那一定是贡献的最小的,那么排序后算一下后缀和

某个学校可能一个队伍都组不起起来，那么用 unordered_set<ll>res存可以组成队伍的学校下标，

要是组不起来，那就erase

（这样就保证不会每次遍历的

我还有一个优化，（虽然时间改变不大187ms到156ms的）就是当要求组队人数大于最大的学校的人数时，那一定输出0

还有下面MLE的部分（为什么报WA？）我赛时发现初始化一直拉到最满（n），是不会WA2的,

赛后将初始化写在前面也是改成n，时间竟然一模一样，哎

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int MAX = 2e5 + 10;
const int INF = 1e9 + 7;
vector<ll> a[MAX];
ll u[MAX];
ll s[MAX];int main() {int T;scanf("%d", &T);while (T--) {int n;scanf("%d", &n);ll maxx = -1;for (int i = 1; i <= n; i++) {scanf("%lld", &u[i]);maxx = max(maxx, u[i]);}//for (int i = 1; i <= maxx; i++) a[i].clear();//可能会MLE，srds显示的是wa/** 假设第一次maxx = 7在第7个有2e5个数据，* 然后第二次maxx = 6，只清空了前6个数据，假设在第6个有2e5个数据，* 。。。* vecotr会炸的*/for (int i = 1; i <= n; i++) {scanf("%lld", &s[i]);}for(int i = 1; i <= n; i++) {a[u[i]].push_back(s[i]);}ll poss = -1;for (int i = 1; i <= n; i++) {poss = max((ll) a[i].size(), poss);}unordered_set<ll>res;for (int i = 1; i <= maxx; i++) {sort(a[i].begin(), a[i].end());for (int j = a[i].size() - 2; j >= 0; j--) {a[i][j] += a[i][j + 1];}res.insert(i);}for (int i = 1; i <= poss; i++) {ll tmp = 0;vector<ll> jian;for (auto j : res) {ll pos = a[j].size() % (i);if (pos < a[j].size())tmp += a[j][pos];if(a[j].size() < i) jian.push_back(j);}for (auto x:jian) res.erase(x);printf("%lld ", tmp);}for (int i = poss + 1; i <= n; i++) {printf("0 ");}printf("\n");for (int i = 1; i <= maxx; i++) a[i].clear();}
}