传送门
题目大意：有一个恶龙有多个头，勇士雇佣人砍掉他所有的头， 每个勇士的能力为x的话，佣金也为x， 能力为x的勇士能砍掉直径为小于等于x的头。这个勇士想花最少的佣金砍掉恶龙所有的头。每个勇士只能雇佣一次。水～～～～
解题思路：算是贪心法吧，一开始我想到的是进行匹配。对恶龙和佣兵进行排序，从小到大遍历恶龙，找到最小的勇士砍对应的头。如果勇士不够就不能砍掉所有的头。代码写完跟题解差不多...原来这也叫贪心。
AC代码：
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int dragon[20005]; int warrior[20005]; int main() { int n, m; while(scanf("%d%d", &n, &m) && m+n) { for(int i=0;i<n; i++) scanf("%d", &dragon[i]); for(int i=0;i<m; i++) scanf("%d", &warrior[i]); sort(dragon, dragon+n); sort(warrior, warrior+m); int ok = 1; int sum = 0; for(int i=0, j = 0; i<n; i++, j++) { while(warrior[j] < dragon[i] && j < m) j++; if(j == m) { ok = 0; break; } sum += warrior[j]; } if(ok) printf("%d\n", sum); else printf("Loowater is doomed!\n"); } return 0; }