[ZOJ3365 Integer Numbers]【排序】【二分】

【题目大意】
给定一个序列，让你改变最少的数，使之变成形如这样的模式x,x+1,x+2,x+3….x+n。
【算法分析】
不考虑改变什么数，只考虑不用改变什么数，如果不用改变的话，那么当且仅当i-a[i]为同样的值。
而且最终结果不可能全都改变，所以可以以i-a[i]把他们分类，个数最多的一类就可以作解，最后输出即可。
这里面用到类似离散化的思想，中途用二分找位置。当然，hash也是可以的。
【其它】1Y
【CODE】
#include #include #include #include using namespace std;
const int N=50000;
int n;
int a[N];
int F[N],L[N];

void solve(){
int l,r,mid,i,ans=0,Maxi;
for (i=0;i l=0; r=n-1;
while (l mid=l+r>>1;
if (L[mid] else r=mid;
}
F[l]++;
}
for (i=0;i if (F[i]>ans){
ans=F[i];
Maxi=i;
}
printf("%dn",n-ans);
for (i=0;i if (i!=0) putchar(‘ ‘);
printf("%d",i-L[Maxi]);
}
putchar(‘n’);
}

int main(){
while (scanf("%d",&n)+1){
int i;
for (i=0;i scanf("%d",&a[i]);
L[i]=i-a[i];
F[i]=0;
}
sort(L,L+n);
solve();
}
}