题目链接：Codeforces Round 961 (Div. 2)
总结：B1wa两发可惜，C出得有点小慢。
A. Diagonals
fag：贪心
Description：给定一个 n ∗ n n * n n∗n的棋盘，给定 k k k个棋子，每个格子只能放一个棋子，求将棋子全部放入棋盘，至少需要占几条对角线。
Solution：求最少占用，显然贪心处理，从最长的对角线开始占用，对角线长度为 n , n − 1 , n − 1 , n − 2 , n − 2 , . . . , 1 , 1 n, n - 1, n - 1, n - 2, n - 2, ..., 1, 1 n,n−1,n−1,n−2,n−2,...,1,1。
void solve(){
cin >> n >> k;
int res = 0;
if (k == 0){
cout << 0 << endl;
}
else{
if (k <= n)
cout << 1 << endl;
else{
res = 1;
k -= n;
for (int i = n - 1; i; i --){
k -= i;
res ++;
if (k <= 0){
cout << res << endl;
return;
}
k -= i;
res ++;
if (k <= 0){
cout << res << endl;
return;
}
}
}
}
}
B1. Bouquet (Easy Version)
fag: 模拟
Description：有 n n n种花，每种花只用一朵，每种花的花瓣为 a i a_i ai，售价也为 a i a_i ai。你有 m m m元钱，问你最多能够买到多少花瓣（任意两朵花的花瓣之差不能超过 1 1 1）。
Solution：easy版，解法很多。这里使用前缀和+二分。
- 先按花瓣数从小到大排序。然后开始枚举，二分找到当前花瓣 + 1的最大下标 t t t；花费不超过 k k k的最大下标 t t tt tt，取 m i n ( t , t t ) min(t, tt) min(t,tt)。
Competing：第一发细节错误；第二发没考虑到花费不超过 k k k的下标，认为满足花瓣数的都能买。
void solve(){
cin >> n >> k;
vector<int> a(n + 1);
vector<int> s(n + 1);
for (int i = 1; i <= n; i ++){
cin >> a[i];
}
sort(a.begin(), a.end());
for (int i = 1; i <= n; i ++){
s[i] = s[i - 1] + a[i];
}
int res = 0;
for (int i = 1; i <= n; i ++){
if (a[i] > k)
continue;
int t = upper_bound(a.begin() + 1, a.end(), a[i] + 1) - a.begin();
int tt = upper_bound(s.begin() + 1, s.end(), s[i - 1] + k) - s.begin();
if (tt <= t){
res = max(res, s[tt - 1] - s[i - 1]);
}
else{
res = max(res, s[t - 1] - s[i - 1]);
}
}
cout << min(k, res) << endl;
}
B2. Bouquet (Hard Version)
fag：思维 + 贪心
Description：与easy的区别为，每种花有 c i c_i ci朵。
Solution：考虑使用花瓣数为 i i i和 i + 1 i +1 i+1的花，先尽可能使用买第一种花，剩下的买第二种花；然后尽可能使用第二种花替代第一种花即可。
Competing：应该是能想到的吧，毕竟只能买两种花
void solve(){
cin >> n >> k;
vector<pii> a(n);
for (int i = 0; i < n; i ++)
cin >> a[i].fi;
for (int i = 0; i < n; i ++)
cin >> a[i].se;
sort(a.begin(), a.end());
int ans = 0;
for (int i = 0; i < n; i ++){
// 尽可能买第一种花
int t = k / a[i].fi;
t = min(t, a[i].se);
ans = max(ans, t * a[i].fi);
if (a[i].fi + 1 != a[i + 1].fi || i + 1 == n)
continue;
// 剩下的买第二种花
int res = k - t * a[i].fi;
int tt = res / a[i + 1].fi;
tt = min(tt, a[i + 1].se);
res = res - tt * a[i + 1].fi;
ans = max(ans, k - res);
if (t == 0)
continue;
// 还剩多少
tt = a[i + 1].se - tt;
ans = max(ans, k - res + max(0LL, min({res, tt, t})));
if (ans == k){
cout << ans << endl;
return;
}
}
cout << ans << endl;
}
C. Squaring
fag：分析
Description：给定一个数组，可以执行任意次操作，每次操作将每个数变为它的平方，求该数组变为不递减数组的最小操作次数。
Solution：显然，我们直接从前往后操作即可，但是直接平方会导致数很大，从而爆longlong。
- 那我们试试记录前面的数执行了多少次操作，根据开始两数之前的关系能否得出该数应该执行的操作次数。
- 对两个数取对数， 2 x a i < = 2 y a i + 1 2^xa_{i} <= 2^ya_{i+ 1} 2xai<=2yai+1，我们发现两个数的操作次数 x , y x, y x,y只与最开始的值有关。
- 我们开始预处理：如果 a [ i ] < a [ i − 1 ] a[i] < a[i - 1] a[i]<a[i−1],我们令 b [ i ] b[i] b[i]为 a [ i ] > = a [ i − 1 ] a[i] >= a[i - 1] a[i]>=a[i−1]的操作次数；如果 a [ i ] = = a [ i − 1 ] a[i] == a[i - 1] a[i]==a[i−1]，令 b [ i ] = = 0 b[i] == 0 b[i]==0。如果 a [ i ] > a [ i − 1 ] a[i] > a[i - 1] a[i]>a[i−1]，令 b [ i ] b[i] b[i]等于负的 a [ i − 1 ] a[i - 1] a[i−1]大于等于 a [ i ] a[i] a[i]的操作次数，相当于可以少执行几次操作。但是我们要注意如果刚好可以令 a [ i ] = = a [ i − 1 ] a[i] == a[i - 1] a[i]==a[i−1],那么 b [ i ] b[i] b[i]不变，否则 b [ i ] b[i] b[i]需要加 1 1 1，因为此时 a [ i − 1 ] > a [ i ] a[i - 1] > a[i] a[i−1]>a[i]了。
void solve(){
cin >> n;
vector<int> a(n);
vector<int> b(n);
for (int i = 0; i < n; i ++){
cin >> a[i];
}
int ans = 0;
for (int i = 1; i < n; i ++){
if (a[i] < a[i - 1]){
if (a[i] == 1){
cout << -1 << endl;
return;
}
else{
int t = a[i];
int c = 0;
while (t < a[i - 1]){
t *= t;
c ++;
}
b[i] = c;
}
}
else if (a[i] == a[i - 1]){
b[i] = 0;
}
else{
int t = a[i - 1];
if (t == 1)
continue;
int c = 0;
while (t < a[i]){
t *= t;
c ++;
}
if (t == a[i])
b[i] = -c;
else
b[i] = -c + 1;
}
}
for (int i = 1; i < n; i ++){
b[i] += b[i - 1];
if (b[i] < 0)
b[i] = 0;
ans += b[i];
}
cout << max(ans, 0LL) << endl;
}