1 条题解
-
2
这道题考试也是挂完了,挂分亡这一块(qwq)
T1还没有题解,来一发吧
正文:
题意简述: 把不规则分散的n个数通过将最外面的数移到自己左边/右边(总之就是往里面移,非端点)的空格,然后整成n个连起来的数所需要的最多&最少移动次数
解法: 最少: 因为可以直接移到里面任意位置,所以可以找内部一个区间n内包含牛最多的区间,将其他不在这个区间的牛通过一次变换移进来即可(可以自己画图证明这个方法,不过有一些特判,一会再说)
方法就是遍历一遍数组,用队列用类似单调队列的方式模拟(就是过了这个区间就从队列前踢掉,把这个加进队列)复杂度为 。最后用n减这个最大区间中数就是最小值
最大: 因为有一个规则(其实我在考试的时候也是想到题目中一句话有了思路:“可以看到随着时间的推移,这样的移动可以使奶牛们趋向越来越近。”)
既然一定会更近,就让他们互相靠近的更短。而一次最短的移动一定是两个(或者多个)贴在一起,然后最左边移到这坨右边第一个(或反过来)这样蠕动一定是最不优的,因为这一坨这一次移动只能移动 ,所以我们只需要找左右两边哪边组成一坨(就是最右边移到次右边的左边一格,或反过来)所需要移动的距离最短,然后滚雪球一样蠕动最后找到最左边的就可以了,需要蠕动的次数就是 + 从最左到最右的空格数(可以推公式)
然后就剩最后一点,就是一些特例: 这种一大坨的然后后面还有孤零零一格的情况,最小会做成 ,而最小应该是 ,需要特判,而还有一种更特殊的情况:
这种情况结果就是 ,只需要 移到 就可以了,要在上个特判的情况下再加一个特判(这个我考试时就没想到)
就是这样了
代码如下:
#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
- 上传者