NOWCODER 新田忌赛马（贪心）

题意：

已知齐威王的马的出场顺序和每只马的速度和刀币数，给田忌的马排序，求能获得的最大刀币数。

题解：

贪心的每次取最大刀币
用比它速度快的所有马中最慢的和它比，得到刀币$ans+=a[i].d$ans+=a[i].d
如果没有比它快的马,失去刀币$ans-=a[i].d$ans−=a[i].d

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
struct Horse{
    int s,d;
}a[maxn];
int n,t,tmp,ans;
multiset<int> s;
multiset<int>::iterator it;
bool cmp(Horse a, Horse b){
	return (a.d==b.d ? a.s<b.s: a.d>b.d);
}
int main(){
    cin>>t;
    while(t--){
    	s.clear(),ans=0;
        cin>>n;
        for(int i=0;i<n;i++) cin>>a[i].s;
        for(int i=0;i<n;i++) cin>>a[i].d;
        for(int i=0;i<n;i++) cin>>tmp,s.insert(tmp);
        sort(a,a+n,cmp);
		for(int i=0;i<n;i++){
        	it = s.upper_bound(a[i].s);
        	if(it==s.end()){
        		ans-=a[i].d;
        		continue;
			}
			ans+=a[i].d;
			s.erase(it);
		}
		cout<<ans<<endl;
    }
}