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++ ,