CF #643 div.2 ABDE

CF #643 div.2 ABDE

一个月没打cf了，难得打一次，结果D被fst了，又掉分
cf太卡了不想进，因此以下代码仅供参考，不保证ac

A题 Sequence with Digits

就是给你一个数n,问你执行k-1次操作后变成多少。
操作：找到n中最大的数和最小的数，n加上这个数。
例如 487 487 487，第一次操作： 487 + ( 4 × 8 ) = 519 487+(4times8)=519 487+(4×8)=519，第二次操作： 519 + ( 1 × 9 ) = 528 519+(1times9)=528 519+(1×9)=528
这题给的数据是 k < 1 e 16 k<1e16 k<1e16，一时间无从下手，我先写了BD才回过头来看A，先写了一个暴力模拟的代码，跑了一会发现，k大了之后n就不会变了，因为很快，n中就会出现0，当n中有0时，可以直接break输出

代码：略

B题 Young Explorers

题意：给出n个人的价值，每个人有价值ki，价值为k的人所在的队伍中至少有k个人，问你这些人最多能组成多少队伍。
其实仔细一想，要使队伍数量最大。价值为1的人必然自成一队，价值为2两人一队，以此类推。
然后第一次我用map记录一下每种价值的人数，然后除一下相加。wa了。
然后想到了1 2 2 2 3 3 这组数据，这样的答案应该是3：1、22、233。
因此只要把前面余下的人加到后面即可。
代码：

map<int, int> mp;
int main()
{int n;cin >> n;while (n--){int temp;cin >> temp;mp[temp]++;}int temp = 0;for (auto it = mp.begin(); it != mp.end(); it++){it->second += temp;temp = it->second % it->first;}int ans = 0;for (auto it = mp.begin(); it != mp.end(); it++)ans += it->second / it->first;cout << ans << endl;return 0;
}

D题 Game With Array

构造题
给出一个 N N N和 S S S，问你能不能给出一个 N N N长度的序列，和为 S S S，并且求出一个 K ( 0 ≤ K ≤ M ) K(0le Kle M) K(0≤K≤M)，使得序列中的某些元素和不为 K K K
例如， N = 5 N=5 N=5 K = 10 K=10 K=10
那么可以给出序列 1 1 1 1 1 1 1 1 1 1 1 1 6 6 6， K = 5 K=5 K=5，这样在序列中找不到和为 5 5 5的子序列。
但是如果 N = 5 N=5 N=5 K = 9 K=9 K=9
不论如何构造序列，都可以找到和为 K ( 0 ≤ K ≤ 9 ) K(0le Kle 9) K(0≤K≤9)的子序列
有两种构造方式：
第一种，序列的前 N − 1 N-1 N−1项都为1，第 N N N项只要 ≥ N + 1 ge N+1 ≥N+1即可，这样是找不到和为 N N N的子序列的。构造条件： S − ( N − 1 ) ≥ ( N − 1 ) + 2 S-(N-1)ge (N-1)+2 S−(N−1)≥(N−1)+2
第二种，序列的前 N − 1 N-1 N−1项都为2，第 N N N项只要 ≥ 2 ge 2 ≥2即可，这样是找不到和为 1 1 1的子序列的。构造条件： S − 2 × ( N − 1 ) ≥ 2 S-2times (N-1)ge 2 S−2×(N−1)≥2
可以发现，经过移项，两种构造方式的构造条件都是一样的

第一种构造方式代码

int main()
{int n, s;cin >> n >> s;if (s >= n * 2) //s - n + 1 >= n - 1 + 2{cout << "YESn";for (int i = 1; i <= n - 1; i++)cout << 1 << ' ';cout << s - n + 1 << endl;cout << n << endl;}elsecout << "NOn";return 0;
}

E题 Restorer Distance

给你 n n n个用 a i ai ai个相同的砖块垒成的柱子，可以选择三种操作：
add：给一个柱子加一块砖块，代价为a
remove：给一个柱子减一块砖块，代价为r
move：将一个柱子的砖块移到另一个柱子上，代价为m
问你要使n个柱子高度相同，最少代价是多少
显然，move操作是可以用a+r取代的。
三分高度mid。
关于三分，还是不太理解三分区间，有空再看看

ll p[100010];
ll n, a, r, m;
ll f(ll mid)
{ll ct1, ct2; //add和remove的数量ct1 = ct2 = 0;for (ll i = 1; i <= n; i++)if (p[i] < mid)ct1 += mid - p[i];elsect2 += p[i] - mid;ll ct3 = min(ct1, ct2); //需要move的数量ct1 -= ct3, ct2 -= ct3;return ct1 * a + ct2 * r + ct3 * m;
}
int main()
{cin >> n >> a >> r >> m;m = min(a + r, m);for (ll i = 1; i <= n; i++)cin >> p[i];sort(p + 1, p + 1 + n);ll l = 0, r = 1000000000;while (l < r){// ll mid = l + r >> 1;// ll midr = mid + r >> 1;ll mid = l + (r - l) / 3; //不太懂ll midr = l + (2 * r - 2 * l + 2) / 3;if (f(mid) > f(midr))l = mid + 1;elser = midr - 1;}cout << f(l) << endl;return 0;
}