当前位置:编程学习 > C/C++ >>

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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,