1 条题解

  • 2
    @ 2026-10-29 17:25:17

    这道题考试也是挂完了,挂分亡这一块(qwq)

    T1还没有题解,来一发吧

    正文:

    题意简述: 把不规则分散的n个数通过将最外面的数移到自己左边/右边(总之就是往里面移,非端点)的空格,然后整成n个连起来的数所需要的最多&最少移动次数

    解法: 最少: 因为可以直接移到里面任意位置,所以可以找内部一个区间n内包含牛最多的区间,将其他不在这个区间的牛通过一次变换移进来即可(可以自己画图证明这个方法,不过有一些特判,一会再说)

    方法就是遍历一遍aa数组,用队列用类似单调队列的方式模拟(就是过了这个区间就从队列前踢掉,把这个ii加进队列)复杂度为 nn。最后用n减这个最大区间中数就是最小值

    最大: 因为有一个规则(其实我在考试的时候也是想到题目中一句话有了思路:“可以看到随着时间的推移,这样的移动可以使奶牛们趋向越来越近。”)

    既然一定会更近,就让他们互相靠近的更短。而一次最短的移动一定是两个(或者多个)贴在一起,然后最左边移到这坨右边第一个(或反过来)这样蠕动一定是最不优的,因为这一坨这一次移动只能移动 11,所以我们只需要找左右两边哪边组成一坨(就是最右边移到次右边的左边一格,或反过来)所需要移动的距离最短,然后滚雪球一样蠕动最后找到最左边的就可以了,需要蠕动的次数就是 11 + 从最左到最右的空格数(可以推公式)

    然后就剩最后一点,就是一些特例: 11 22 33 44 55 88 这种一大坨的然后后面还有孤零零一格的情况,最小会做成 11,而最小应该是 22,需要特判,而还有一种更特殊的情况:

    11 22 33 44 66

    这种情况结果就是 11,只需要 11移到 55 就可以了,要在上个特判的情况下再加一个特判(这个我考试时就没想到)

    就是这样了

    代码如下:

    #include<bits/stdc++.h>
    using namespace std;
    void lhhsyn(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0); 
    }
    int n;
    int a[100005],b[100005];
    int q[100005],sz,fr,ba;
    int res=-1e9,ans;
    void lhh(){
    	int cnt=0,cnt1=0;
    	int l=0,r=0;
    	for(int i=1;i<=n;i++){
    		if(b[i]==0){
    			cnt++;
    			if(l==0)l=i-1;
    			r=i;
    		}
    	}
    	if(cnt==n){
    		cout<<0<<"\n";
    		return;
    	}
    	if(cnt==n-1){
    		if(l==2&&a[l]-a[1]==2||r==n-1&&a[n]-a[r]==2){
    			cout<<1<<"\n";
    			return;
    		}
    		cout<<2<<"\n";
    		return;
    	}
    	fr=0,ba=0;
    	for(int i=1;i<=n;i++){
    		while(sz>0&&a[i]-a[q[fr]]>=n){
    			res=max(res,sz);
    			fr++;
    			sz--;
    		}
    		q[ba++]=i;
    		sz++;
    		res=max(res,sz);
    	}
    	cout<<n-res<<"\n";
    } 
    void syn(){
    	cout<<a[n]-a[1]-n+1-min(b[2],b[n]);
    }
    int main(){
    	lhhsyn(); 
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    	}
    	sort(a+1,a+n+1);
    	for(int i=2;i<=n;i++){
    		b[i]=a[i]-a[i-1]-1;
    	}
    	lhh();
    	syn();
    	return 0;
    } 
    
    

    给个赞喵

    信息

    ID
    944
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    (无)
    递交数
    50
    已通过
    10
    上传者