UVALive 7146
题意
自己有n个军队 敌方有m个军队
每个军队都有攻击力和防守力两种属性
当一方的攻击力>=对方的防御力时 可以把对方杀掉
在一次战斗中有可能出现双方都死了或者双方都没死的情况
另外要求己方不能有两只不同军队跟对方的同一只军队交战
问是否能全歼敌军
如果可以的话，输出最多可以存活多少只己方军队
我们队的做法稍微有点复杂,我尽量解释得清楚一点：
a数组存己方军队，b数组存地方军队
先把a[]按防御力升序排，把b[]按攻击力升序排
然后分别给b[]、a[]数组赋一个编号值ID
b[i].ID = b[i]的攻击力在b[]中是第几弱 + 1
a[i].ID = 能跟b[]中攻击力第(ID - 1)弱的打完不死的【此处不保证能杀掉对方】（攻击力相同的只计一次）
如果跟谁打都死 那么ID = 1
eg： 若ID = 3，那么他能跟b[]中攻击力第二弱（攻击力是次小值）
每个ID会分到一个堆，是关于防御力的小根堆
然后再把a[]按攻击力降序排，把b[]按防守力降序排
这时候最外层循环是b[]中的军队
每次把a[]中能打败b[i]的军队对应的优先队列并插入
等把所有能打败b[i]的军队插入以后，此时所有优先队列中的所有a[]都是能杀掉b[i]的
（之前插入的a[?]攻击力更高，所以更能杀掉b[i]）
此时要从中分配一个a[?]去打b[i]
如果有可能有军队可以杀完b[i]后活下来，那么要选ID >= b[i].ID并且防御力最少的，这样残血活下来最经济
如果谁去都是死，那么就找一个所有优先队列中防御力最低的去打即可
关于a[]
对于每个相同ID，之所以要采用堆，是因为要把每次询问的复杂度降到O(logn)
对于不同的ID，如果采用优先队列数组，每次询问从头到尾扫一遍，每次查找都是O(n)，那么整体就还是n方
这时候要采用线段线段树
每个叶子节点依次对应一个堆 然后其值为1时代表堆非空 0则表示堆空
线段树记录区间和
这样可以快速找到大于等于b[i].ID且堆非空的最小ID号，取出根节点即为应该与b[i]交战的军队
如果找不到这样的ID号，就照大于等于1且堆非空的最小ID号
如果还找不到，说明无解
#include <iostream> #include <cstdlib> #include <cstdio> #include <algorithm> #include <iostream> #include <cstring> #include <cmath> #include <queue> using namespace std; typedef long long ll; const int maxn = 100000; struct Node{ int A,D,ID; }; priority_queue<int, vector<int>, greater<int> > que[maxn+10]; struct tree{ int l, r, data; }T[maxn*4]; void buildTree(int now ,int l, int r) { int lson = now<<1, rson = lson|1; T[now].l = l; T[now].r = r;T[now].data = 0; if(l == r) return; int mid = (l+r)>>1; buildTree(lson, l, mid); buildTree(rson, mid+1, r); } void change(int now, int aim) { int lson = now<<1, rson = lson|1; if(T[now].l == aim && T[now].r == aim) { T[now].data ^= 1; return; } int mid = T[lson].r; if(aim <= mid) change(lson, aim); else change(rson, aim); T[now].data = T[lson].data+T[rson].data; } int getSum(int now, int index) { int lson = now<<1, rson = lson|1; if(T[now].r == index) return T[now].data; int mid = T[lson].r; if(index <= mid) return getSum(lson, index); else return T[lson].data+getSum(rson, index); } int findPos(int now, int aim) { int lson = now<<1, rson = lson|1; if(T[now].data < aim) return 0; if(T[now].l == T[now].r) return T[now].l; if(T[lson].data < aim) return findPos(rson, aim-T[lson].data); else return findPos(lson, aim); } bool cmpD(Node a, Node b) { return a.D<b.D; } bool cmpA(Node a, Node b) { return a.A<b.A; } Node a[maxn+10],b[maxn+10]; void init(int cnt) { buildTree(1, 1, cnt); for(int i = 1; i <= cnt; i++) while(!que[i].empty()) que[i].pop(); } int main() { //freopen("in2.txt", "r", stdin); int T; scanf("%d", &T); int kase = 0; while(T--) { int n,m; printf("Case #%d: ", ++kase); scanf("%d%d", &n, &m); for(int i = 0; i < n; i++) scanf("%d%d", &a[i].A, &a[i].D); for(int i = 0; i < m; i++) scanf("%d%d", &b[i].A, &b[i].D); if(m > n) { printf("-1 "); continue; } sort(a,a+n,cmpD); sort(b,b+m,cmpA); int cnt = 2, cnta = 0; int ans = 0; for(int i = 0; i < m; i++) { b[i].ID = cnt; while(i < m-1 && b[i+1].A == b[i].A) b[++i].ID = cnt; while(cnta < n && a[cnta].D <= b[i].A) a[cnta++].ID = cnt-1; //if(cnta == n && i != m) {ans = -1;break;} cnt++; } for(int i = cnta; i < n; i++) a[i].ID = cnt-1; sort(a, a+n, cmpA); sort(b, b+m, cmpD); for(int i = n-1; m-n+i >= 0; i--) if(a[i].A < b[m-n+i].D) { ans = -1; break; } if(ans == -1) { printf("-1 "); continue; } init(cnt); cnta = n-1; for(int i = m-1; i >= 0; i--) { while(a[cnta].A >= b[i].D && cnta >= 0) { if(que[a[cnta].ID].empty()) { change(1, a[cnta].ID); } que[a[cnta].ID].push(a[cnta].D); cnta--; } int id = b[i].ID; int sum = getSum(1, id-1); int index = findPos(1, sum+1); if(index == 0) { ans++; int tmp = 1; int ind = findPos(1,1); que[ind].pop(); if(que[ind].empty()) change(1, ind); } else { que[index].pop(); if(que[index].empty()) change(1, index); } } printf("%d ", n-ans); } return 0; }