codeforces gym 100947 J. Killing everything dp+二分
4 seconds
64 megabytes
standard input
standard output
There are many enemies in the world such as red coders and hackers. You are trying eliminate everybody. Everybody is standing on a road, which is separated into 109 sections. The sections are numbered 1, 2, 3, 4, …109 from west to east. You want to kill N enemies. The ith enemy will be standing on the section Ai. In order to kill the enemies, you prepared P small bombs and Q large bombs. You can choose a positive integer w as a parameter for energy consumption. Then, a small bomb can kill all enemies in at most w consecutive sections, and a large bomb can kill all enemies of at most 2w consecutive sections.
Enemies can be killed by more than one bomb. You want to kill all enemies. Since it is expected that many civilians will walk down that road, for the sake of safety, you have to fix the positions of the bombs and minimize the value of w.
So you decided to Write a program that, given information of the enemies and the number of bombs, determine the minimum value of w so all enemies can be killed.
The input consists of several test cases, the first line contains the number of test cases T. For each test case: The first line of input contains three space separated integers N, P, Q (1 ≤ N ≤ 2000, 0 ≤ P ≤ 105, 0 ≤ Q ≤ 105), where N is the number of the enemies, P is the number of small bombs, and Q is the number of large bombs.
The ith line (1 ≤ i ≤ N) of the following N lines contains an integer Ai, the section where the ith enemy will be standing.
Output: For each test cases print the solution of the problem on a new line.
1
3 1 1
2
11
17
4
In the sample test case you have 3 enemies at positions: 2, 11, 17.
For w = 4, one possible solution is to throw one small bomb on segment 1 - 4, and one large bomb on segment 11 - 18. This configuration will kill all three enemies.
There is no configuration with w < 4 that can kill them all.
题意:给你n个位置,p个小炸弹,q个大炸弹;小炸弹可以连续炸w长度,大炸弹可以连续炸2*w长度
思路:显然二分答案求最小的w,问题在于如何check;
dp[i][j]表示炸完i之前所有点,使用j个小炸弹,最少需要多少个大炸弹;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<bitset>
#include<time.h>
using namespace std;
#define LL long long
#define pi (4*atan(1.0))
#define eps 1e-4
#define bug(x) cout<<"bug"<<x<<endl;
const int N=2e3+,M=5e5+,inf=1e9+,mod=1e9+;
const LL INF=1e18+,MOD=1e9+; int n,p,q;
int nex[N][];
int dp[N][N],a[N];
int check(int x)
{
for(int i=;i<=n;i++)
{
nex[i][]=lower_bound(a+,a+n+,a[i]+x)-a;
if(*x-inf+a[i]>)nex[i][]=n+;
else nex[i][]=lower_bound(a+,a+n+,a[i]+x+x)-a;
}
for(int i=;i<=n+;i++)
{
for(int j=;j<=p;j++)
dp[i][j]=inf;
}
dp[][]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=p;j++)
{
int v=nex[i][];
dp[v][j+]=min(dp[v][j+],dp[i][j]);
v=nex[i][];
dp[v][j]=min(dp[v][j],dp[i][j]+);
}
}
for(int i=;i<=p;i++)
if(dp[n+][i]<=q)return ;
return ;
}
int main()
{
int T,cas=;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&p,&q);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
if(p+q>=n)
{
printf("1\n");
continue;
}
sort(a+,a++n);
a[n+]=inf*;
int s=;
int e=inf,ans=-;
while(s<=e)
{
int mid=(s+e)>>;
//cout<<mid<<endl;
if(check(mid))
e=mid-,ans=mid;
else s=mid+;
}
printf("%d\n",ans);
}
return ;
}
最新文章
- 二十、Java基础--------IO流之其他对象
- hibernate的Criteria条件查询
- AchartEngine的柱状图属性设置
- [Asp.net mvc] 在Asp.net mvc 中使用MiniProfiler
- [改善Java代码]构造代码块会想你所想
- [Javascript] Drawing Styles on HTML5 Canvas
- NodeJS加MongoDB应用入门
- ";System.Web"; 中不存在类型或命名空间
- Linux编程环境介绍(2) -- shell(Bash) 介绍
- java 构造方法 constructor demo笔记
- Codeforces B. Divisiblity of Differences
- Windows内置安全主体
- git中利用rebase来压缩多次提交 ----- 原文:https://blog.csdn.net/itfootball/article/details/44154121
- C++ vector的用法(整理)
- vue的指令
- c++过程
- CF932F Escape Through Leaf 斜率优化、启发式合并
- TECH books
- Qt 使用QMovie加载gif图片实现动态等待窗口
- linux centos5.8装yum安装mysql