# Defeat the Enemy UVALive – 7146

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,

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

#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 ;
}

python开发_常用的python模块及安装方法

Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…

zengkefu@server1:/usr/src\$ uname -aLinux server1 4.10.0-19-generic #21…

Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…

Struts的使用

400-888-8888

ceotheme@ceo.com