U5398 改数(num)

• • 5通过
  • 28提交
• 题目提供者52zyz
• 标签
• 难度尚无评定

 提交  

最新讨论

• 暂时没有讨论

题目背景

又是一年NOIP，科学馆的五楼：“我们看下这道题,我们来模拟一下…2,3,5,7,12…这其实就是一个a[i+1]-a[i]=i的序列……”那熟悉的凌波教鞭，熟悉的憨厚的声音，那熟悉的...哦，还有那熟悉的来自未来某位神牛的发言：“老师，好像有个数写错了……”

题目描述

给出一个长度为n的整数序列a，你能改动最少的数，使之满足a[i+1]-a[i]=i(1<=i<n)么?

输入输出格式

输入格式：

 

输入第一行包含一个整数n

第二行包含n个整数，分别表示a[1]到a[n]。

 

输出格式：

 

输出一个整数，表示最少改多少个数。

 

输入输出样例

输入样例#1：
5 1 2 4 5 11 输出样例#1：
1

说明

对于30%的数据N<=1000

对于100%的数据1<=N<=100000

输入的其他数据的绝对值均小于等于109

AC代码+题解：

/* 一种想法是可以枚举每一个数，将它固定，然后根据固定的数求出别的数，更新答案；这样是O(n^2)的； 根据这个理论，可以将每一个数固定，然后直接求出a1，看那个a1相同的次数最多，那个就是答案。 */ #include<cstdio> #include<algorithm> #include<iostream> #define N 100010 using namespace std; int a[N],num[N],zh1[N],n; int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);num[i]=num[i-1]+i-1;zh1[i]=a[i]-num[i];}sort(zh1+1,zh1+n+1);int tot=0,p=1,ans;for(int i=2;i<=n;i++){if(zh1[i]!=zh1[i-1]){if(p>tot)tot=p,ans=zh1[i-1];p=1;}else p++;}if(p>tot) ans=zh1[n];tot=0;for(int i=1;i<=n;i++) if(a[i]!=ans+num[i])tot++;printf("%d",tot);return 0; }

 

转载于:https://www.cnblogs.com/shenben/p/5967878.html

与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的U5398 改数(num)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。