【cf】CodeForces Round 890(Div.2)题解 A - C
A. Tales of a Sort
题意
给出一个数组,每次操作可以将 ==所有== 元素 $a[i]$ 变成 $max(0,a_i-i)$,问至少操作多少次能将数组变成递增数组
思路
这一题卡很久,最后发现踩了两个坑
- 题目读错了,每次操作会改变所有元素,而不是指定元素!
- 元素 $a[i]>=0$ ,不用考虑负数情况!
我的思路是,另外开一个数组存储原数组排好序的结果,然后从后往前遍历两个数组,计算出原数组末尾有多少元素是已经排好序的,我们在操作的时候就可以不考虑这些元素,直接将未排序的部分全部变成 0 即可,答案就是未排序部分的最大值
代码
|
B. Good Arrays
题意
给出一个数组a
如果数组b满足:
- ab的相同位上元素都不相等
- ab数组元素的总和相等
就称b是good数组
现在问是否存在一个good的数组b
思路
这题的思路超级简单,在输入数组a中元素的时候记录下数组a元素的总和sum
和数组a中有多少个1,在数组a中是1的位置上,数组b能填的最小值是2,在数组a不是1的位置上,数组b能填的最小值是1,如果数组b能填的最小值的总和小于数组a元素的总和sum
,就说明不存在这样的数组b,反之则存在
代码
|
C. To Become Max
题意
给出一个数组,每次操作可以把其中一个比它后方相邻元素小的元素加1,问最多 k 次操作后数组中的最大值是多少
思路
二分查找答案,首先可以确定答案的最小值lb
就是原数组中的最大值(一次都不操作的情况下),答案的最大值ub
就是原数组中最大值+最大操作次数(所有的操作次数全部用在了最大值上),每次取mid = lb + ub >> 1
作为当前的最大值
然后从 0 到 n - 1 遍历每一个元素 $a[i]$,判断如果最后的数组中最大值是 $a[i]$ 的话,$a[i]$ 能否在 k 次操作内变成 $mid$
这应该怎么判断呢?
经过观察我们可以发现,对 $a[i]$ 进行操作的前提是 $a[i]<=a[i+1]$,所以想要让 $a[i]$ 变成 $mid$,$a[i+1]$ 至少要是 $mid-1$,$a[i+2]$ 至少要是 $mid - 2$,以此类推,$a[j]$ 至少要是 $mid-(j-i)$
- 如果 $a[j]$ 满足条件也就是 $a[j]>=mid-(j-i)$,那么当前的 $a[i]$ 一定可以变成 $mid$,直接返回 true
- 如果 $a[j]<mid-(j-i)$,那我们要想办法把 $a[j]$ 变成 $mid-(j-i)$,因此需要对 $a[j]$ 操作 $mid-(j-i)-a[j]$ 次,由于操作次数有限,如果此时我们剩余的操作次数不够了,就说明 $a[j]$ 不能变成我们想要的数,也就意味着 $a[i]$ 不能变成当前最大值 $mid$
代码
using namespace std;
void solve()
{
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i ++ ) cin >> a[i];
int maxx = *max_element(a.begin(), a.end()); // 找数组中最大值
function<bool(int)> binary = [&](int goal)
{
for (int i = 0; i < n; i ++ ) // 遍历每一个元素 把这个元素变成goal
{
int rest = k; // 还剩余的操作次数
for (int j = i; j < n; j ++ )
{
int require = goal - (j - i); // 把a[i]变成goal需要把a[j]变成require
if (require <= a[j]) return true; // 如果a[j]本来就比require大那肯定成立
int need = max(require - a[j], 0); // a[j]需要操作的次数
if (rest < need) break; // 剩余操作次数不满足就不成立
rest -= need; // 原来的操作次数的基础上减去当前步骤操作次数
}
}
return false;
};
int ans = 0;
int lb = 0;
int ub = maxx + k;
while (lb < ub)
{
int mid = lb + ub + 1 >> 1;
if (binary(mid)) lb = mid; // 答案在右侧
else ub = mid - 1; // 答案在左侧
}
cout << lb << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t -- )
{
solve();
}
}