Description
有n块石头排成一行,从左到右依次编号为1到n,相邻两块石头之间的距离为1。有m只青蛙,开始时都位于1号石头
,它们都需要跳到n号石头上。青蛙只能跳到更靠右的石头上。如果第i只青蛙的某次跳跃的距离超过d,那么需要
付出ci的代价。求出满足以下两个条件时,总代价的最小值:
(1) 石头a1,a2,a3,…,ak必须被跳到恰好一次。
(2) 其它石头(不包含1号石头和n号石头)不能被跳到。
有多组数据。
Input
第一行一个整数t表示数据组数。
每组数据第一行四个整数n,m,k,d,第二行m个整数c1~cm,第三行k个整数a1~ak。
t<=10,3<=n<=10^9,1<=d<=10^9,1<=m,k<=10^5,
1<ai<n,ai互不相同。
Output
每组数据输出一行一个整数表示答案。
Sample Input
2
10 2 3 3
4 7
4 8 7
10 2 2 3
4 7
9 5
Sample Output
4
15
题解
经过观察可以发现,因为所有青蛙的极限距离D是相同的,所以青蛙之间的费用是可以互换的。
同时,我们可以发现,一旦一只青蛙需要付费跳跃一次,我们倒不如让它直接付费从1号石子直接跳跃到n号石子,因为将中间的石子留给其他青蛙,是有概率减少他们付费跳跃的次数的。
所以,我们二分最多可以有多少只青蛙可以同时免费从1号石子跳到n号石子,那么其他青蛙就直接从1号石子付费跳跃到n号石子,免费的那部分明显贪心取费用的最大值。
如果所有青蛙都需要付费跳跃才能完成任务,那么就选取费用最低的青蛙付费跳跃完所有石子,然后其他青蛙直接从1号到n号。
代码
#include <cstdio>
#include <queue>
#include <algorithm>
#define LL long long
using namespace std;
const int MAXN=1e5+50;
queue<int> que;
int c[MAXN], s[MAXN];
int n, m, D, K;
inline int calc(int p){
int ret=0;
while(!que.empty()) que.pop();
for (int i=1; i<=p; i++) que.push(1);
for (int i=1; i<=K; i++){
int now=que.front(); que.pop();
if (s[i]-now>D) ++ret;
que.push(s[i]);
}
for (int i=1; i<=p; i++){
int now=que.front(); que.pop();
if (n-now>D) ++ret;
}
return ret;
}
inline void solve(int T){
scanf("%d%d%d%d", &n, &m, &K, &D);
for (int i=1; i<=m; i++) scanf("%d", &c[i]);
for (int i=1; i<=K; i++) scanf("%d", &s[i]);
sort(c+1, c+m+1);
sort(s+1, s+K+1);
int left=1, right=m, mx=0;
while(left<=right){
int mid=(left+right)/2;
if (calc(mid)==0){
mx=max(mx, mid);
left=mid+1;
}else right=mid-1;
}
LL ans=0;
if (mx==0) {
ans=1LL*calc(1)*c[1];
for (int i=2; i<=m; i++) ans+=c[i];
}else{
for (int i=max(0, m-mx); i>=1; i--) ans=ans+c[i];
}
printf("%lld\n", ans);
}
int main(){
// freopen("in.txt", "r", stdin);
int T=0; scanf("%d", &T);
for (int i=1; i<=T; i++) solve(i);
return 0;
}
发表评论