原题链接:http://codeforces.com/problemset/problem/819/B

题意:把一个数列整体往右移k位(大于n位置的数移动到数列前端,循环滚动),定义该数列的“偏差值”:

求在移动最少k位时,得到的最小“偏差值”。

思路:对于每个数每次往右移,其与i的差值-1,差值记为d,那么记录d>0和d<=0的位置个数;同时记录每个大于0的d的个数,保存在po数组内。

每次往右移,sum加上d<=0的个数,减去d>0的个数,对于将要移动到数列首位置的数,更新差值,进行特判,并更新po数组。

AC代码:

 #include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN = 2e6 + ;
int a[MAXN], cnt_ne = , cnt_po = , d[MAXN];
int ne[MAXN], po[MAXN];
long long sum = ;
int main()
{
int n;
scanf("%d", &n);
memset(ne, , sizeof(ne));
memset(po, , sizeof(po));
for (int i = ;i<n;i++) {
scanf("%d", &a[i]);
d[i] = a[i] - i-;
if (d[i]>) {
cnt_po++;
po[d[i]]++;
}
else {
cnt_ne++;
ne[-d[i]]++;
}
sum += abs(d[i]);
}
int u = ;
long long res = sum;
for (int i = ;i<n;i++) {
//cout << sum << endl;
sum += cnt_ne;
sum -= cnt_po;
cnt_po -= po[i];
cnt_ne += po[i]; d[n - i] -= i - ;//最后一个数更新差值
//再放到第一位,进行判断
if (d[n - i] <= ) {
if (d[n - i] + n - >) {
int dd = d[n - i] + n - - (abs(d[n - i])+);
d[n - i] += n - ;
sum += dd; cnt_po++;
cnt_ne--;
po[d[n - i] + i]++;
}
else sum -= n;
}else sum += n - ; if (res>sum) {
res = sum;
u = i;
}
}
cout << res << ' ' << u << endl;
}

最新文章

  1. 如何写一个简单的http服务器
  2. 《图形学》实验四:中点Bresenham算法画直线
  3. Python之路 day1 用户登录多次被锁定
  4. visualgo 数据结构与算法可视化工具
  5. [转] Asp.Net 导出 Excel 数据的9种方案
  6. Java文件操作源码大全
  7. bash组织成树数据结构
  8. WCF学习——构建第二个WCF应用程序(五)
  9. Java - Spring MVC 实现跨域资源 CORS 请求
  10. [LeetCode] Teemo Attacking 提莫攻击
  11. DIV中文字换行显示
  12. mysql索引及优化
  13. sql 数据库(表空间),用户 相关命令
  14. Group by 内部排序
  15. Hibernate的多对多实例
  16. Diamond 3.5简易教程(一)------工程的建立
  17. python 中使用ConfigParser类修改配置文件
  18. 智能家居入门DIY——【七、添加一个LCD12864吧】
  19. Spring学习-理解IOC和依赖注入
  20. OpenERP Web Client设置闲置有效时间

热门文章

  1. 配置idea中类头注释中的 ${user} 自动获取电脑的名字,怎么去修改名字
  2. Lesson 2 Thirteen equals one
  3. python 并发编程 多进程 互斥锁
  4. Docker数据持久化及实战(Nginx+Spring Boot项目+MySQL)
  5. numpy库的认识以及数组的创建
  6. Linux安装Jenkins并部署springboot项目
  7. 原生js格式化json和格式化xml的方法
  8. windows安装nginx部署
  9. Python 项目转化为so文件
  10. DRF之三大认证