对抗女巫的魔法碎片

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 372    Accepted Submission(s): 94


Problem Description
光明世界的一个国家发生动***巫利用了邪恶的力量将国家的村庄都施下了咒语,好在国家还有英勇 的士兵,他们正义的力量能够破解这些魔咒夺回村庄,并且得到魔法碎片,利用足够多的魔法碎片可以将女巫铲除。
现在己经被魔咒封印的村庄有m个,编号为1到m。英勇的士兵n个,编号从1到n。第i个士兵攻击力 为 ai,第j个村庄防御力为 bj,魔法价值为 cj
现在这些士兵想夺回这些村庄,每个士兵可以最多占领一个村庄,一个村庄最多被一个士兵占领。当士兵的攻击力 ai大于村庄的防御力 bj的时候,该士兵就可以夺回这个村庄,并且士兵会获得魔法碎片 aibj+cj 个。
现在想知道这些士兵夺回村庄,获得的魔法碎片之和最多是多少
 

Input
输入第一行一个整数T,表示有T组数据。
接下来一行输入两个整数n和m。
接下来一行,输入n个数 ai,表示士兵的攻击力。
接下来m行,每行输入两个数 bici,表示村庄的防御力和该村庄的魔法价值。
1 <= n,m <= 100000
1 <=  ai,bi,ci <= 100000
 

Output
一个整数,表示获得的魔法碎片的数量
 

Sample Input
2 3 3 4 4 4 2 3 1 3 5 3 3 3 4 4 6 2 3 4 3 5 3
 

Sample Output
11 10


学习到了multiset的使用姿势。


#include<iostream>
#include<cstring>
#include<set>
#include<algorithm>
# define ll long long 
using namespace std;

int a[100005],b[100005],c[100005],d[100005];
multiset<int>s;  
  
bool cmp(int x, int y)  
{  
    return c[x]-b[x] > c[y]-b[y];  
}  
  
   
  
int main()  
{  
    int n, m, t;  
    scanf("%d",&t);  
    while(t--)  
    {  
        s.clear();  
        scanf("%d%d",&n,&m);  
        for(int i=0; i<n; ++i)  
            scanf("%d",&a[i]);  
        for(int i=0; i<m; ++i)  
        {  
            scanf("%d%d",&b[i],&c[i]);  
            d[i] = i;  
        }  
        sort(a, a+n, greater<int>());  
        sort(d, d+m, cmp);  
        if(n > m) n = m;  
        for(int i=0; i<n; ++i)  
            s.insert(a[i]);  
        int cnt = 0;  
        ll ans = 0;  
        for(int i=0; i<m; ++i)  
        {  
            int id = d[i];  
            multiset<int>::iterator it = s.upper_bound(b[id]);  
            if(it == s.end()) continue;  
            ++cnt;  
            ans += c[id]-b[id];  
            s.erase(it);  
        }  
        for(int i=0; i<n&&i<cnt; ++i)  
            ans += a[i];  
        printf("%lld\n",ans);  
    }  
    return 0;  
}