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