【题解】天才ACM

题目链接

解题思路

既然是有已定的t,那可以想到要么倍增要么二分。
对于二分,如果每次T很小会造成很多不必要的时间浪费,所以我们选择倍增
而每一次询问我们都要找到区间内最小的几个和最大的几个做方差。每次sort(l,r+p)的时间复杂度较大,所以我们选择对于有序区间(l,r-1)和sort(r,r+p)进行归并排序,即将原有序数组于新增数组归并排序。可以将时间复杂度降至 $O(NlogN)$ 。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,t;
int a[500005],atmp[500005],s[500005];
bool isok(int l,int r,int p){
    for(int i=l;i<=r+p;i++)s[i]=a[i];
    sort(s+r+1,s+r+p+1); 
    int lp=l,rp=r+1,cnt=l;
    while(lp<=r&&rp<=r+p){
        if(s[lp]>s[rp])atmp[cnt++]=s[rp++];
        else atmp[cnt++]=s[lp++];
    }
    for(int i=lp;i<=r;i++)atmp[cnt++]=s[lp++];
    for(int i=rp;i<=r+p;i++)atmp[cnt++]=s[rp++];
    
    int dui=min(m,(p+r-l+1)/2);
    long long ans=0;
    for(int i=0;i<dui;i++){
        ans+=(long long)(atmp[r+p-i]-atmp[l+i])*(atmp[r+p-i]-atmp[l+i]);
    }
    if(ans>t)return false;//如果不成功的话不能将a[i]赋值为atmp[i]。 
    //因为我们维护的是可行段的顺序。 
    else{
        for(int i=l;i<=r+p;i++)a[i]=atmp[i]; 
        return true;
    }
}
signed main(){
    int k;
    cin>>k;
    for(int cas=1;cas<=k;cas++){
        memset(atmp,0,sizeof(atmp));
        memset(s,0,sizeof(s));
        cin>>n>>m>>t;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        int l=1;
        int answer=0;
        while(l<=n){
            int p=1,r=l;
            while(p!=0){
                if(r+p>n)p=n-r;
                if(isok(l,r,p)){
                    r+=p;
                    p*=2;
                    if(r>=n)break;
                }else{
                    p/=2;
                }
            }
            answer++;
            l=r+1;
        }
        cout<<answer<<endl;
    }
    return 0;
}

本文链接:http://kaispace.com.cn/index.php/archives/682/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者