CodeChef Consecutive Snakes 三分(整数)
题意
在年度阅兵中,所有的士兵蛇都在阅兵场集合了,但这些蛇的站位不对。整场阅兵必须能从主席台看清楚,所有蛇都应该站成一排。但这些士兵非常懒惰,你必须指挥士兵重新排队,使得所有人的移动距离之和最短。
形式化地,整支阅兵队伍可以视作一条数轴。共有N条蛇,每条蛇是一根长度为L的线段。第i条蛇初始时占据了[Si,Si + L]的区间,蛇与蛇之间可以重合。能从主席台看到的只有区间[A,B],因此所有的蛇都应该处于这个区间内。蛇应该排列成连续一段,之间不能留缝隙,即这些蛇从前往后应该依次占据[X,X+L],[X +L,X+2L], ...,[X+(N−1)L,X+NL] 这些区间,其中A<=X<=X+NL<=B。保证 [A,B] 足以排下所有的蛇。
如果一条蛇初始时位于 [X1,X1+L],重排后位于 [X2,X2+L],那么这条蛇的移动距离为|X2−X1|。你需要将蛇重新排列,使得排列后满足上述条件,并最小化所有蛇的移动距离之和。
你需要输出最短距离和。
数据
输入的第一行包含一个整数T,代表测试数据的组数。接下来是T组数据。
每组数据第一行包含四个整数N、L、A和B,分别代表蛇的条数、蛇的长度,以及从主席台可见的区间[A,B]。
接下来一行包含N个整数S1, S2,..., SN,代表每条蛇初始所处区间的左端点。
对于每组数据,输出一行,包含一个整数,代表最短距离和。
1<=T<=10; 3<=N<=1e5; 1<= Si,L<=1e9; 1<=A<=B<=1e9; NL<=B-A
输入
2
3 4 11 23
10 11 30
3 4 11 40
10 11 30
输出
16
16
说明
第一组数据中,三条蛇初始时位于 [10,14]、[11,15]、[30,34] 三个区间。一种最优解是将第1条蛇移动到 [15,19],第 3 条蛇移动到 [19,23]。移动距离和为|15−10|+|11−11|+|19−30| = 5+0+11 = 15。
第二组数据相较于第一组,只是主席台能看到的区间更大了而已。而事实上,最优解不变。
题解:
第一条蛇的左边端点可以三分,所以我们三分这个点,算一算花费就可以了。特别要注意的是三分的左右边界。
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
const long long INF = 1e18+1LL;
const double Pi = acos(-1.0);
const int N = 1e5+, M = 1e3+, mod = ,inf = 2e9; int a[N],n,L,A,B,T;
LL cal(int x) {
LL sum = ;
for(int i = ; i <= n; ++i) {
sum += abs(x - a[i]);
x += L;
}
return sum;
}
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d%d%d%d",&n,&L,&A,&B);
for(int i = ;i <= n; ++i) scanf("%d",&a[i]);
sort(a+,a+n+);
int l = A, r = B - n*L;
while(l + < r) {
int x = (r - l)/ + l;
int y = (r - l)/ * +l;
LL sum1 = cal(x);
LL sum2 = cal(y);
if(sum1 >= sum2) l = x;
else r = y;
}
LL ans = cal(l);
for(int i = l; i <= r; ++i)
ans = min(ans,cal(i));
cout<<ans<<endl;
}
return ;
}
CONSESNK: 连续的蛇
题目描述
在年度阅兵中,所有的士兵蛇都在阅兵场集合了,但这些蛇的站位不对。整场阅兵必须能从
主席台看清楚,所有蛇都应该站成一排。但这些士兵非常懒惰,你必须指挥士兵重新排队,使得
所有人的移动距离之和最短。
形式化地,整支阅兵队伍可以视作一条数轴。共有 N 条蛇,每条蛇是一根长度为 L 的线段。
第 i 条蛇初始时占据了 [Si
, Si + L] 的区间,蛇与蛇之间可以重合。能从主席台看到的只有区间
[A, B],因此所有的蛇都应该处于这个区间内。蛇应该排列成连续一段,之间不能留缝隙,即这
些蛇从前往后应该一次占据 [X, X + L], [X + L, X + 2L], . . . , [X + (N − 1)L, X + NL] 这些区间,
其中 A ≤ X ≤ X + NL ≤ B。保证 [A, B] 足以排下所有的蛇。
如果一条蛇初始时位于 [X1, X1 + L],重排后位于 [X2, X2 + L],那么这条蛇的移动距离为
|X2 − X1|。你需要将蛇重新排列,使得排列后满足上述条件,并最小化所有蛇的移动距离之和。
你需要输出最短距离和。
输入格式
输入的第一行包含一个整数 T,代表测试数据的组数。接下来是 T 组数据。
每组数据第一行包含四个整数 N、L、A 和 B,分别代表蛇的条数、蛇的长度,以及从主席
台可见的区间 [A, B]。
接下来一行包含 N 个整数 S1, S2, . . . , SN,代表每条蛇初始所处区间的左端点。
输出格式
对于每组数据,输出一行,包含一个整数,代表最短距离和。
数据范围与
• 1 ≤ T ≤ 10
• 3 ≤ N ≤ 105
• 1 ≤ Si
, L ≤ 109
• 1 ≤ A ≤ B ≤ 109
• NL ≤ B − A
样例数据
输入
2
3 4 11 23
10 11 30
3 4 11 40
10 11 30
输出
16
16
1
SnackDown Pre-elimination Round A 2017
样例解释
第一组数据中,三条蛇初始时位于 [10, 14]、[11, 15]、[30, 34] 三个区间。一种最优解是将第 1 条蛇移
动到 [15, 19],第 3 条蛇移动到 [19, 23]。移动距离和为 |15−10|+|11−11|+|19−30| = 5+0+11 = 15。
第二组数据相较于第一组,只是主席台能看到的区间更大了而已。而事实上,最优解不变。
最新文章
- 由于启动用户实例的进程时出错,导致无法生成 SQL Server 的用户实例。该连接将关闭。
- 解决umount.nfs: /data: device is busy 问题
- iOS使用Safari调试UIWebView
- php和.net 的加密解密
- 在ASP.NET项目中使用CKEditor +CKFinder实现图片上传功能
- Install PhoneGap
- JAVA设计模式(09):结构化-代理模式(Proxy)
- CSS.06 -- 尚合网页模拟
- NowCoderWannafly挑战赛5-可编程拖拉机比赛-向上取整和向下取整函数
- [经验分享] MySQL Innodb表导致死锁日志情况分析与归纳【转,纯学习】
- Eclipse配置“运行时依赖路径”
- mysqli链接数据库
- ios中input获取焦点时的问题
- React-state props与render()的关系
- [转载]linux段页式内存管理技术
- python摸爬滚打之day01----初识Python
- javascript_ajax 地址三级联动
- Java获取函数参数名称
- Notepad++ xml/json格式化
- CodeVS 1017 DP
热门文章
- 【模板】CDQ分治
- 大数据学习——采集目录到HDFS
- Python+selenium(定位一组元素)
- xtu DP Training C.炮兵阵地
- Linux基础之重定向|grep
- [luoguP3178] [HAOI2015]树上操作(dfs序 + 线段树 || 树链剖分)
- msp430项目编程27
- MySQL的字符串连接函数CONCAT, CONCAT_WS,GROUP_CONTACT
- 51 Nod 1244 莫比乌斯函数前n项和
- HDU1533 最小费用最大流