題意：有n個士兵和m件武器，每個武器都有一定的重量，每個士兵能拿武器的重量有一個范圍，為minw和maxw，求最多能有多少個士兵拿到武器。
思路：這是昨天下午和武大集訓隊一起做的第一場比賽，被虐無懸念。剛開始看到這道題的時候我想到的是貪心，提交了一次wa，然後就開始想其他的思路，後來又想到了二分匹配，但是因為邊太多（n為2500，m為40000），不出所料的tle了，之後就一直悲劇到最後了，最後也沒過。就出了兩道大水題，，，，，
正確思路：貪心。按每個人區間的左端點排序，然後正著循環倒著循環都可以。需要注意的是，正著循環的時候，需要考慮一種情況，就是一個區間包含另一個區間的情況，這種情況要特殊處理一下。可以在排序的時候提前處理即可。倒著循環的時候就沒有這種情況了。
代碼：
[cpp] www.2cto.com
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
const int N = 3000,M = 41000;
struct sold{
int maxw,minw;
}ss[N];
bool cmp(sold a,sold b){
if(a.minw == b.minw)
return a.maxw < b.maxw;
else if(a.minw > b.minw && a.maxw <= b.maxw)
return true;
else if(a.minw <= b.minw && a.maxw >= b.maxw)
return false;
return a.minw < b.minw;
}
int main(){
//freopen("1.txt","r",stdin);
int n,m;
while(scanf("%d%d",&n,&m) != EOF){
for(int i = 0;i < n;++i)
scanf("%d%d",&ss[i].minw,&ss[i].maxw);
int weight[M];
for(int i = 0;i < m;++i)
scanf("%d",&weight[i]);
sort(ss,ss+n,cmp);
sort(weight,weight+m);
int sum = 0,flag[M],pos = 0;
CLR(flag,0);
for(int i = 0;i < n ;++i){
for(int j = 0;j < m;++j){
if(ss[i].minw <= weight[j] && weight[j] <= ss[i].maxw && !flag[j]){
sum++;
flag[j] = 1;
pos = j+1;
break;
}
}
}
printf("%d\n",sum);
}
return 0;
}
作者:wmn_wmn
