ZOJ 3508 The War 贪心

题意：有n个士兵和m件武器，每个武器都有一定的重量，每个士兵能拿武器的重量有一个范围，为minw和maxw，求最多能有多少个士兵拿到武器。
思路：这是昨天下午和武大集训队一起做的第一场比赛，被虐无悬念。刚开始看到这道题的时候我想到的是贪心，提交了一次wa，然后就开始想其他的思路，后来又想到了二分匹配，但是因为边太多（n为2500，m为40000），不出所料的tle了，之后就一直悲剧到最后了，最后也没过。就出了两道大水题，，，，，
正确思路：贪心。按每个人区间的左端点排序，然后正着循环倒着循环都可以。需要注意的是，正着循环的时候，需要考虑一种情况，就是一个区间包含另一个区间的情况，这种情况要特殊处理一下。可以在排序的时候提前处理即可。倒着循环的时候就没有这种情况了。
代码：
[cpp]   www.zzzyk.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

补充：软件开发 , C++ ,