Codeforces Round #694 (Div. 2)
A. Strange Partition
题意
给一个正整数数组，每次可以把相邻两个数合并成它们的和。每个数除以 向上取整，再加起来，问这个和最小和最大分别是多少。
思路
先分别取整会把每一项的零头都算进去，合并以后零头可能凑在一起，答案只会减小。所以最大值就是一个也不合并，最小值就是全部合成一个数。
一边求总和，一边累加每项向上取整的结果就行，时间 。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 17;
ll t, x, n, a[maxn];
ll ans1, ans2;
int main() {
cin >> t;
while(t--) {
cin >> n >> x;
ans1 = 0, ans2 = 0;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) ans1 += a[i], ans2 += (a[i] / x + ((a[i] % x) ? 1 : 0));
ans1 = (ans1 / x + ((ans1 % x) ? 1 : 0));
cout << ans1 << " " << ans2 << endl;
}
return 0;
}B. Strange List
题意
从头依次处理数组。当前数 能被 整除，就在末尾加上 个 ；碰到第一个不能整除的数就停。问最后整个数组的和。
思路
一个数拆成 份以后，新增的总和还是这个数。按轮来看，每完整处理一轮，就多出一份原数组的总和。
b[i] 记 最多能除几次 ，其中最小值是 mb。前 mb 轮都能完整处理，下一轮会停在第一个 b[i] == mb 的位置，所以它前面的数还能各贡献一份。
答案就是 (mb + 1) * s[n] + s[p]，其中 p 是这个位置的前一个下标。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 17;
const int oo = 0x3f3f3f3f;
int n, t, x, a[maxn], b[maxn], mb, p;
ll s[maxn];
int main() {
cin >> t;
while(t--) {
cin >> n >> x;
for(int i = 1; i <= n; i++) cin >> a[i];
mb = oo, p = 0;
for(int i = 1; i <= n; i++) {
b[i] = 0;
for(int t = a[i]; t % x == 0; t /= x) b[i]++;
mb = min(mb, b[i]);
s[i] = s[i - 1] + 1ll * a[i];
}
for(int i = 1; i <= n; i++) {
if(b[i] == mb) {
p = i - 1;
break;
}
}
cout << 1ll * (mb + 1) * s[n] + s[p] << endl;
}
return 0;
}C. Strange Birthday Party
题意
有 个朋友和 件礼物，第 件价格是 ，价格按编号不降。给第 个朋友，可以买一件编号不超过 的礼物，也可以直接给 元；每件礼物只能买一次。问最少花多少钱。
思路
把 从大到小排，便宜礼物优先给直接发钱最贵的人，这样省得更多。第一个人尝试第 1 件，第二个人尝试第 2 件，只要 i < k[i]，就把他的花费改成 c[i]。
遇到 k[i] <= i 就停。后面的 只会更小，剩下的礼物也不会更便宜，直接发钱就行。排序后扫一遍，时间 。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn = 3e5 + 17;
int n, t, m, k[maxn], c[maxn];
long long ans;
bool cmp(int x, int y) {
return x > y;
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &k[i]);
for(int i = 1; i <= m; i++) scanf("%d", &c[i]);
sort(k + 1, k + 1 + n, cmp);
for(int i = 1; i <= m; i++) {
if(k[i] > i) k[i] = i;
else break;
}
for(int i = 1; i <= n; i++) ans += 1ll * c[k[i]];
printf("%lld\n", ans);
ans = 0;
for(int i = 1; i <= n; i++) k[i] = 0;
for(int i = 1; i <= m; i++) c[i] = 0;
}
return 0;
}