codeforces Fish Weight

本文从WordPress迁移而来, 查看全部WordPress迁移文章

贪心 构造

题意:有k种鱼,重量是非递减的(即允许相同)。A拿了n条鱼,给出每条鱼的种类,B拿了m条鱼,给出每条鱼的种类。两人各自算出自己的鱼的总重量,问A的总重量能否严格大于B的总重量,每种鱼的重量是未知的,由你来决定的,就是问你,在你的控制下, 能否令A的总重量超过B,如果无论如何都无法超过,则输出NO,否则YES

这题是div2的第4题,其实比较水,关键是要主要的,k种鱼的重量是允许相同的,这就好办了,利用贪心的原则,尽量消掉B的大鱼

给A和B的鱼分别按重量排序,从各自最重的鱼开始。如果B当前最大的鱼比A大(编号大),那么就让A的鱼和B的鱼重量相等,这样就可以用一条A鱼消掉一条B鱼。如果在A鱼还没用完的情况下,出现了一条B鱼的编号比A小,这时候就可以见风使舵,将将B剩下来的鱼的重量都设为一个非常小的数(已经排了序,后面的鱼只会更小),那么就算B鱼全部加起来都没有A这条鱼大

正是因为允许鱼的重量可以为浮点数并且相等,才有了贪心的可能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100010
#define pb push_back

int n,m,k,a[N],b[N];

int main(){
while(scanf("%d%d%d",&n,&m,&k)!=EOF){
for(int i = 0; i < n; i++)
scanf("%d",&a[i]);
for(int i = 0; i < m; i++)
scanf("%d",&b[i]);
sort(a,a+n);
sort(b,b+m);
int indexa = n - 1 ,indexb = m - 1;
while(indexa >= 0 && indexb >= 0){
if(b[indexb] >= a[indexa])
indexa-- , indexb--;
else break;
}
if(indexa >= 0) puts("YES");
else puts("NO");
}
return 0;
}