题目链接:http://codeforces.com/problemset/problem/820/D

题目大意:

  给出一个\(n\)元素数组\(p[]\),定义数组\(p[]\)的误差值为\(\sum\limits_{i=1}^{i=n} |p[i]-i|\).每次操作都把下标为\(n\)的数放到下标为\(1\)的位置,其他数依次右移,问在通过几次操作后能使得误差值最小

知识点:  (void)

解题思路:

  见注释。

AC代码:

 #include <bits/stdc++.h>

 using namespace std;
typedef long long ll;
const int maxn=1e6+;
ll p[maxn],has[maxn<<]; int main(){
ll n;
ll bigger=,smaller=,equ=,ans1=,ans2=; //bigger 记录目前比其下标大的数的个数,small 记录比其下标小的,equ 记录等于其下标的,最终输出是 ans1 ans2
scanf("%I64d",&n);
for(ll i=1LL;i<=n;i++){
scanf("%I64d",&p[i]);
if(p[i]>i){
bigger++;
has[p[i]-i]++; //has[X] 记录比下标大 X 的数的个数
}
else if(p[i]==i){
equ++;
has[]++;
}
else smaller++;
ans1+=abs(p[i]-i);
}
ll temp=ans1; //临时记录ans1 //首先,请注意:我后面提到的数字其实都是数字与下标的差值,因为我们着重研究的是这个
for(ll last=n-1LL,now=1LL;last>=1LL;last--,now++){ //last 记录目前下标为n的数的位置;now 记录目前是第几号变换,在此处理解为一条“零线”,除了下标为n的数之外的所有数减去 now 即为现在的数
temp+=(equ+smaller);
temp-=bigger; //从 now-1 变换到 now 后,所有数的下标加一(不考虑下标为n的数),则原来小于或等于下标的数对于ans1的贡献值增大1,大于下标的数对于ans1的贡献值减小1 smaller+=equ; //原本等于下标的数都变成小于了
bigger-=has[now]; //原本等于 now+1(即现在的now, 其实就是原本等于1)的数现在都变成了0
//接下来处理之前下标是n,现在下标是1的数
if(p[last+]>=last+1LL)
has[p[last+]-last-]--; //先抹除其原来在has[]中的记录
has[p[last+]-+now]++; //重新记录,注意:此时的“零线”已经抬高了,相应的也要加上 now
equ=has[now]; //新的equ其实就是那些现在在“零线”上的数
if(p[last+]>1LL) bigger++;
smaller=n-equ-bigger; //显然,smaller + equ + bigger = n temp-=abs(p[last+]-n-1LL); //特殊处理原本下标为n的数
temp+=abs(p[last+]-1LL);
if(temp<ans1){
ans1=temp;
ans2=now;
}
}
printf("%I64d %I64d\n",ans1,ans2); return ;
}

  

最新文章

  1. html代码转义到js时,往往会遇到问题,这代码实现html和js互转
  2. Codeforces Round #378 (Div. 2) D. Kostya the Sculptor map+pair
  3. matlab 画锥体
  4. NYOJ-36 最长公共子序列 AC 分类: NYOJ 2014-01-03 20:54 155人阅读 评论(0) 收藏
  5. Huffman Coding 哈夫曼编码
  6. tomcat+apache 实现负载均衡之一:同一台电脑部署2个以上tomcat
  7. 诡异的XmlSerializer属性字段Specified
  8. c语言函数---M
  9. javascript基础-闭包
  10. Docker(九):Docker容器卷插件
  11. 2.7 C++构造函数
  12. webgl 混合
  13. Allure Report使用
  14. 八月(The Summer is Gone)观后感
  15. mvcpager 表单提交时无法获取pageindex的值
  16. Linux学习5-初学者注意事项
  17. 关于inherit的笔记
  18. html5中script的async属性
  19. 关于In-App Purchase(内购)的注意事项
  20. v2.0 组件通信的总结

热门文章

  1. js 之 箭头函数 (未学完)
  2. optparse--强大的命令行参数处理包
  3. linux之centos安装jdk以及nginx详细过程
  4. puppet报告系统Dashboard部署及配置详解
  5. Spring LDAP的使用
  6. 字符串后面空字符的问题(char*与string的转换)
  7. python(time 模块)
  8. muduo网络库源码学习————线程安全
  9. 封锁阳光大学(染色)P1330
  10. Pycharm修改HTML模板