zoj3365——Integer Numbers

44424742

题意：给定一串数字，求改变最少的次数，使得其为连贯的递增序列。
思路：由于要的是d=1的递增序列，则任意a[i]-i=d，寻找出现最多那个d的个数num。求得需更换的次数为n-num。同时，自己推一下，就可以将序列输出。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define maxn 50005int a[maxn],b[maxn],c[maxn];int main(){int i,n;while(scanf("%d",&n)!=EOF){for(i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i]-i;c[i]=b[i];}sort(b+1,b+n+1);int maxnum=0,temp;int j;i=1;while(1){if(i>n) break;j=i+1;while(j<=n&&b[i]==b[j]){j++;}if(j-i>maxnum) { maxnum=j-i;temp=b[i];}i=j;}printf("%d\n",n-maxnum);for(i=1;i<n;i++)printf("%d ",a[i]-(c[i]-temp));printf("%d\n",a[n]-(c[n]-temp));}return 0;}