Codeforces Round 842 Div. 2 A-B题解

2023/1/6 C++ Codeforces 算法竞赛 Round 842 Div. 2 题解

憋问为什么只有A-B🤡

A.Greatest Convex

题面

先化个简，
要找的x的范围是在1,2,...,k-1,要使x尽可能大
看一下k-1是否符合要求，

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        int k;
        cin>>k;
        cout<<k-1<<'\n';
    }
    return 0;
}

B. Quick Sort

题面

去找找每一次操作应该选什么样的数排序之后放到最后.

发现如果要充分利用每次排序，应该选的都是不按顺序出现的数.

如果选过一组(k个)数排序后扔到最后，那么比这些数大的数必然需要重新选中排序(需要排到队尾).
选的数应尽可能大，小的数能不选就不选.

1可以不管.

如果最后一次选时乱序的数个数比k小，那么可以重新选一些排好序的末尾的数(就在现在序列的末尾)来补充操作的数的个数到k个，这样是可行的.

所以若要使结果最优，可以看从1开始的顺序序列有多长，找到第一个不满足顺序的数cnt.
如[2,5,1,3,4]中最长的从1开始的顺序序列是[1],第一个不满足顺序的数是2.
[1,3,2,4]中最长的从1开始的顺序序列是[1,2],第一个不满足顺序的数是3.

最后需要的操作次数应是

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int p[N];
int v[N];
int ceil(int n,int k)
{
    if(n%k==0)
        return n/k;
    return n/k+1;
}
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        int n,k;
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            cin>>p[i];
            v[p[i]]=i;
        }
        int t=1;
        for(int i=2;i<=n;i++)
        {
            if(v[i]<v[i-1])
            {
                t=i;
                break;
            }
        }
        if(t==1)
            cout<<0<<'\n';
        else
            cout<<ceil(n-t+1,k)<<'\n';
    }
    return 0;
}
img_show