zoj 3508 The War 贪心

2024-08-28 17:32

文章标签 贪心 war zoj 3508

本文主要是介绍zoj 3508 The War 贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

士兵有一个拿武器的重量的范围，给出几种武器的重量，问如何才能让更多的士兵装备武器，求出最大的人数

Description

A war had broken out because a sheep from your kingdom ate some grasses which belong to your neighboring kingdom. The counselor of your kingdom had to get prepared for this war. There are N (1 <= N <= 2500) unarmed soldier in your kingdom and there are M (1 <= M <= 40000) weapons in your arsenal. Each weapon has a weight W (1 <= W <= 1000), and for soldier i, he can only arm the weapon whose weight is between minWi and maxWi ( 1 <= minWi <= maxWi <= 1000). More armed soldier means higher success rate of this war, so the counselor wants to know the maximal armed soldier he can get, can you help him to win this war?

Input

There multiple test cases. The first line of each case are two integers N, M. Then the following N lines, each line contain two integers minWi, maxWi for each soldier. Next M lines, each line contain one integer W represents the weight of each weapon.

Output

For each case, output one integer represents the maximal number of armed soldier you can get.

Sample Input

Sample Output

2
0

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{int u,v;
} q[1000000];
int a[1000000];
int cmp(struct node x,struct node y)
{return x.v<y.v;
}
int main()
{int i,m,n,j,s;while(scanf("%d %d",&n,&m)!=EOF){s=0;for(i=0; i<n; i++)scanf("%d %d",&q[i].u,&q[i].v);for(i=0; i<m; i++)scanf("%d",&a[i]);sort(q,q+n,cmp);sort(a,a+m);for(i=0; i<m; i++){for(j=0; j<n; j++){if(a[i]>=q[j].u&&a[i]<=q[j].v){q[j].u=0;q[j].v=0;s++;a[i]=0;break;}}}printf("%d\n",s);}return 0;
}//这道题目就是每次是的士兵拿的的兵器是排序的最反的其实就是为了扩大可那的空间而已#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{int u,v;
} q[1000000];
int a[1000000];
int cmp(struct node x,struct node y)
{return x.u>y.u;
}
int cmp2(int x,int y)
{return x>y;
}
int main()
{int i,m,n,j,s;while(scanf("%d %d",&n,&m)!=EOF){s=0;for(i=0; i<n; i++)scanf("%d %d",&q[i].u,&q[i].v);for(i=0; i<m; i++)scanf("%d",&a[i]);sort(q,q+n,cmp);sort(a,a+m,cmp2);for(i=0; i<m; i++){for(j=0; j<n; j++){if(a[i]>=q[j].u&&a[i]<=q[j].v){q[j].u=0;q[j].v=0;s++;a[i]=0;break;}}}printf("%d\n",s);}return 0;
}

上面两个代码都是正确的

这篇关于zoj 3508 The War 贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！