题意：
你有n个人，对面有m个人（n，m 1e5）每个人有个攻击和防御，攻击大于等于对方防御可以消灭对方
可以都存活或者都被消灭。现在让你安排一些人跟对面的人单挑，要求全歼对面的人并使自己的伤亡数最少
如果有，输出最小的伤亡数，如果没有这种方案，输出-1.
思路：
维护一个自己的攻击降序和对面的防御降序，然后扫对面的人，每次把攻击大于等于当前对面的防御值的人的防御值加入集合，
如果可以不死，选择一个防御大于对面当前攻击的最小值，如果谁上都要死，那就选个防御最小值就好了（因为当前攻击打后面的人都够用了）。
-1的情况很好判断了。被坑了一次set去重。。改了multiset
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <stack> #include <map> #include <unordered_map> #include <string> #include <time.h> #include <cmath> #include <stdlib.h> #define LL long long #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define ou(a) printf("%d ",a) #define pb push_back #define pii pair<int,int> #define mkp make_pair #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); using namespace std; const int inf=0x3f3f3f3f; const int mod=1e9+7; const int N=1e5+10; int t,n,m; struct wq { int a,b; }a[N],b[N]; bool cmp1(wq a,wq b) { if(a.a!=b.a) return a.a>b.a; return a.b>b.b; } bool cmp2(wq a,wq b) { if(a.b!=b.b) return a.b>b.b; return a.a>b.a; } multiset<int>s; multiset<int>::iterator it; int main() { scanf("%d",&t); for(int cas=1;cas<=t;cas++) { s.clear(); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].a,&a[i].b); for(int i=1;i<=m;i++) scanf("%d%d",&b[i].a,&b[i].b); printf("Case #%d: ",cas); if(n<m) { printf("-1 "); continue; } sort(a+1,a+n+1,cmp1); sort(b+1,b+m+1,cmp2); int ans=n-m,p=1; bool flag=1; for(int i=1;i<=m;i++) { while(p<=n&&a[p].a>=b[i].b) s.insert(a[p].b),p++; if(!s.size()) { flag=0; break; } it=s.upper_bound(b[i].a); if(it==s.end()) s.erase(s.begin()); else ans++,s.erase(*it); } if(flag==0) printf("-1 "); else printf("%d ",ans); } return 0; }