首页 技术 正文
技术 2022年11月23日
0 收藏 311 点赞 3,599 浏览 2724 个字

 

  Long long ago there is a strong tribe living on the earth. They always have wars and eonquer others. One day, there is another tribe become their target. The strong tribe has decide to terminate them!!! There are villages in the other tribe. Each village contains a troop with attack power EAttacki, and defense power EDefensei. Our tribe has troops to attack the enemy. Each troop also has the attack power Attacki, and defense power Defensei. We can use at most one troop to attack one enemy village and a troop can only be used to attack only one enemy village. Even if a troop survives an attack, it can’t be used again in another attack.

  The battle between 2 troops are really simple. The troops use their attack power to attack against the other troop simultaneously. If a troop’s defense power is less than or equal to the other troop’s attack power, it will be destroyed. It’s possible that both troops survive or destroy.

The main target of our tribe is to destroy all the enemy troops. Also, our tribe would like to have most number of troops survive in this war.

Input

  The first line of the input gives the number of test cases, Ttest cases follow. Each test case start with 2 numbers and m, the number of our troops and the number of enemy villages. lines follow, each with Attackand Defensei, the attack power and defense power of our troops. The next lines describe the enemy troops. Each line consist of EAttackand EDefensei, the attack power and defense power of enemy troops

Output

  For each test ease, output one line containing ‘Case #xy’, where is the test case number (starting from 1) and is the max number of survive troops of our tribe. If it‘s impossible to destroy all enemy troops, output ‘-1’ instead.

Limits:

1≤ ≤100,

1≤ n,m ≤105,

1≤ Attacki,Defensei,EAttacki,EDefense≤109,

Sample Input

2

3 2

5 7

7 3

1 2

4 4

2 2

2  1

3  4

1 10

5 6

Sample Output

Case #1: 3

Case #2: -1

很久以前,地球上有一个强大的部落生活着。他们总是有战争和其他人。有一天,有另一个部落成为他们的目标。强大的部落决定终止他们!另一个部落有m个村庄。每个村庄都有一支攻击力量EAttacki和防御力量EDefensei的部队。我们的部落有n个部队来攻击敌人。每个部队还拥有攻击力Attacki和防御力Defensei。我们最多可以使用一个部队攻击一个敌方村庄,部队只能用来攻击一个敌方村庄。即使一个部队在袭击中幸存,它也不能在另一次袭击中再次使用。

两支部队之间的战斗非常简单。部队利用其攻击力同时攻击对方。如果一个部队的防御力小于或等于另一部队的攻击力,它将被破坏。两个部队都有可能生存或摧毁。

我们部落的主要目标是摧毁所有的敌军。此外,我们的部落希望在这场战争中有大量的部队生存下来。

这题和我的上一篇随笔差不多,一样的原理,stl在ACM里面作用非常大啊

注意multiset的运用

 #include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<cctype>
using namespace std;
struct node {
int x,y;
} a[],b[];
int cmp1(node a,node b) {
return a.x>b.x;
}
int cmp2(node a,node b) {
return a.y>b.y;
} int main() {
int n,t,cas=,m;
scanf("%d",&t);
while(t--) {
scanf("%d%d",&n,&m);
multiset<int>ms;
multiset<int>::iterator it;
for (int i= ; i<n ; i++)
scanf("%d%d",&a[i].x,&a[i].y);
for (int i= ; i<m ; i++)
scanf("%d%d",&b[i].x,&b[i].y);
sort(a,a+n,cmp1);
sort(b,b+m,cmp2);
int ans=,flag=;
for (int i= ,j=; i<m ; i++ ) {
while(j<n && a[j].x>=b[i].y ) {
ms.insert(a[j++].y);
}
if (ms.empty()) {
flag=;
break;
}
it=ms.upper_bound(b[i].x);
if (it==ms.end()) it=ms.begin();
if (*it<=b[i].x) ans++;
ms.erase(it);
}
printf("Case #%d: %d\n",cas++,flag?(n-ans):-);
}
return ;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/140721.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,075
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,505
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,317
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,311
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,912
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,099
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站