Codeforces 1631 D. Range and Partition —— 尺取,贪心,一点点想法

This way

题意:

给你n个数,你要将其分成k个区间,并且任意一个区间中,值在[x,y]中的数的个数要大于值不在[x,y]中的数的个数。问你y-x要最小的话,x和y分别是什么,并且要将这k个区间的左右端点输出。

题解:

嗨呀,果然是水题以前做太少基础都不扎实了,做到这种有那么一点点需要思考的题目才找回感觉嘛。

怎么找x,y使得y-x最小?我最直接的想法就是从小到大枚举y的时候确定x,如何确定才能避免时间复杂度变成O(N^2).尺取。

由于尺取的时间复杂度为O(N),因此我们不能将检查当前情况正确性的时间复杂度变为O(N),如何进行快速的检查?

这就需要你找到一个性质:由于每个区间中,在[x,y]的数量要至少比不在[x,y]的数量大1,那么假设在[x,y]中的值我们看成1,不在[x,y]中的值我们看成-1.要使得最后的区间能够至少k个,所有值加起来要>=k.原因自己探究,我是列了一些样例感觉是对的就没有深思。
所以我们只需要在尺取的时候检查当前在[x,y]中的数量要比不在[x,y]中的数量至少大k即可。
但是最后要你求出这个区间到底怎么分呢?
我们知道区间是连续的,那么每一个-1一定要找左边或者右边离他最近的1来消掉负面影响,我就使用了一个set存所有1的位置。
并且找到了之后,将当前的-1和对应的1的值变为0,代表他们的正负影响抵消了。
那么最后这个数组只剩下了1和0.那么我们只需要将其分成k个区间,并且保证每个区间值的和至少是1即可。那么我这里使用了贪心,从左往右找,只要和为1,就输出。因为1的数量一定是>=k的,所以正确性能保证,但注意第k个区间要特殊处理,将剩下的所有位置给包括即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int num[N],a[N],b[N];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
        sort(b+1,b+1+n);
        int all=unique(b+1,b+1+n)-b-1;
        for(int i=1;i<=n;i++)
            num[int(lower_bound(b+1,b+1+all,a[i])-b)]++;
        int l=1,r=1,s=0;
        int ansl,ansr,ans=1e9;
        while(r<=all){
            s+=num[r];
            if(s-(n-s)>=k){
                while(s-num[l]-(n-s+num[l])>=k)s-=num[l++];
                if(b[r]-b[l]<ans)ans=b[r]-b[l],ansl=b[l],ansr=b[r];
            }
            r++;
        }
        printf("%d %d\n",ansl,ansr);
        set<int>st;
        for(int i=1;i<=n;i++){
            b[i]=(ansl<=a[i] && a[i]<=ansr)?1:-1;
            if(b[i]==1)
                st.insert(i);
        }
        for(int i=1;i<=n;i++){
            if(b[i]==-1){
                set<int>::iterator it=st.upper_bound(i);
                if(it!=st.begin())it--;
                b[i]=b[*it]=0;
                st.erase(it);

            }
        }
        l=1,r=1,s=0;
        for(int i=1;i<k;i++){
            while(s==0)s+=b[r++];
            s=0;
            printf("%d %d\n",l,r-1);
            l=r;
        }
        printf("%d %d\n",l,n);
        for(int i=1;i<=all;i++)num[i]=0;

    }
}

上一篇:《DDIA》读书笔记:分区


下一篇:Doris之动态分区