题目
描述
题目大意
一个序列，每次可以使一段区间内的所有数加一（模四）。
问最少的操作次数。
思考历程
一看这题目，诶，这不就是那道叫密码锁的题目吗？
然后随便打一打，样例过了，就再也没有思考这一题。
正解
其实我的想法完全错了。
因为这题只能加，不能减啊！
于是就得考虑另一个方法。
题目可以转成这样的问题：给你一个数列，你可以预先给其中的数加四，然后每次对一个区间进行减一操作，问最少的操作数。
显然，如果已经加四了，就是一道大水题（好像叫……粉刷栅栏）？
我们先不考虑加四，那么答案就是
然后我们考虑加四会有什么影响。
现在我们考虑一下，假设有两个高地为和，中间的比较低，要把它们降下来，能不能通过抬高中间的，使得操作数尽量小呢？
然后开始按照和之差和和之差分类讨论。
接着就可以发现，只有的情况是有意义的。
于是我们扫一扫有没有这样的东西，减去它们的贡献就好了。
要注意，如果一起做，有可能搞完了，就没办法搞了。
由于更优，所以先从左到右将它给搞掉。
接着重新搞剩下两种。
然后就可以做出来了，说实在的，这方法让我醉了……
还有一种比较强大的做法，没有分类讨论。
刚开始的操作是一样的，同样是计算出一个暂时的答案。
然后从前往后扫，如果现在走的是下坡路，就将高度差存入一个桶中。
如果在走上坡路，记高度差为，就在桶种找小于的第一个有值的，记为。
如果找到了就让答案减去，然后在桶中的值减一，在桶中的值加一。
这样就可以计算出答案了。
具体原因什么的……感觉上有些玄学，我是感性理解的。
代码
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
int n;
int a[N],c[N];
int las[N];
int main(){
int T;
scanf("%d",&T);
while (T--){
scanf("%d",&n);
for (int i=1;i<=n;++i)
scanf("%d",&a[i]);
for (int i=1;i<=n;++i){
int x;
scanf("%d",&x);
a[i]=(x-a[i]+4)%4;
}
int ans=0;
for (int i=0;i<=n;++i){
ans+=max(a[i+1]-a[i],0);
c[i]=a[i+1]-a[i];
}
memset(las,255,sizeof las);
int cnt2=0,cnt3=0;
for (int i=0,j=-1;i<=n;++i)
if (c[i]==-3){
cnt3++;
las[i]=j;
j=i;
}
else if (c[i]==3 && cnt3){
cnt3--;
c[j]=c[i]=0;
j=las[j];
ans-=2;
}
cnt3=0;
for (int i=0;i<=n;++i)
if (c[i]==-2)
cnt2++;
else if (c[i]==-3)
cnt3++;
else if (c[i]==2 && cnt3)
cnt3--,ans--;
else if (c[i]==3 && cnt2)
cnt2--,ans--;
printf("%d
",ans);
}
return 0;
}
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
int n;
int a[N];
int buc[4];
int main(){
int T;
scanf("%d",&T);
while (T--){
scanf("%d",&n);
for (int i=1;i<=n;++i)
scanf("%d",&a[i]);
for (int i=1;i<=n;++i){
int x;
scanf("%d",&x);
a[i]=(x-a[i]+4)%4;
}
int ans=0;
for (int i=1;i<=n;++i)
ans+=max(a[i]-a[i-1],0);
memset(buc,0,sizeof buc);
for (int i=1;i<=n;++i)
if (a[i-1]>a[i])
buc[a[i]-a[i-1]+4]++;
else{
int j=0;
for (;j<a[i]-a[i-1];++j)
if (buc[j])
break;
if (buc[j]){
buc[j]--,buc[a[i]-a[i-1]]++;
ans-=a[i]-a[i-1]-j;
}
}
printf("%d
",ans);
}
return 0;
}
总结
分类讨论是一种很恶心的方法……
另一种说法叫做：面向数据编程