首页 > ACM题库 > HDU-杭电 > HDU 2863-Top Shooter-贪心-[解题报告]HOJ
2014
02-17

HDU 2863-Top Shooter-贪心-[解题报告]HOJ

Top Shooter

问题描述 :

Since the Border War in 1962, Both China and India abide by the principle of no-expansion of military power, but India’s recent actions are obviously going against this principle. Indian Prime Minister Singh delivered a speech in Congress, said that "regardless of face of China or other countries, India will, by all means to ensure the territorial integrity, national unity and security."
At the same time, India increases more than sixty thousand troops to the southern Tibetan, including the construction of five airports and advanced landing field. Obviously this behavior undermines the trust between the two countries. Aggressive as a result of India, China announced the establishment of commando in Tibet!

The commando consists of N snipers. Messages show that Indian will send airborne to our Border. Our Army organizes the commando ambushing in the mountains.
A sniper can only hit the target in his field of vision. And will not be able to hit the target outside his field of vision
As the captain of the commando, how will you show your talent to win the battle?

输入:

The input consists of several test cases. The first line of each case contains two integers N, M (1<=N<=50, 1<=M<=1000), N representing the number of snipers, M representing the number of airborne. The next line contains N numbers (Hi,(1<=i<=N)), representing each sniper’s field of vision.(the field of vision Hi means that the sniper can only see the target higher than or equal to Hi meters), The next M lines contain a pair of integers(Ai,Hi) each, representing the airborne i (1<=i<=M) begin to fall at the moment Ai, and from the height Hi,(1<=Ai<=100,1<=Hi<=500).
We assume that each airborne falls one meter per second, a sniper can only hit one target per second.

输出:

The input consists of several test cases. The first line of each case contains two integers N, M (1<=N<=50, 1<=M<=1000), N representing the number of snipers, M representing the number of airborne. The next line contains N numbers (Hi,(1<=i<=N)), representing each sniper’s field of vision.(the field of vision Hi means that the sniper can only see the target higher than or equal to Hi meters), The next M lines contain a pair of integers(Ai,Hi) each, representing the airborne i (1<=i<=M) begin to fall at the moment Ai, and from the height Hi,(1<=Ai<=100,1<=Hi<=500).
We assume that each airborne falls one meter per second, a sniper can only hit one target per second.

样例输入:

2 5
1 9
1 2
1 2
1 2
2 2
2 4

样例输出:

4

#include <list>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#include <stack>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <limits.h>
#include <time.h>
#include <string.h>
using namespace std;

#define LL long long
#define PI acos(-1.0)
#define Max INT_MAX
#define Min INT_MIN
#define eps 1e-8
#define FRE freopen("a.txt","r",stdin)
#define N 1001
priority_queue<int , vector<int> ,greater<int> > p[701];
int s[51];
int n,m;
bool vis[51];
int live,die;
void gao(){
    int i,j,k;
    live=0,die=0;
    int t=1;
    while(live+die<m){
        i=0;
        while(i<n && !p[t].empty()){
            int x=p[t].top();
            p[t].pop();
            if(x>=s[i]){
                die++;
                i++;
            }
            else
            if(x-1>=s[0]){
                x--;
                p[t+1].push(x);
            }
            else
            live++;
        }
        while(!p[t].empty()){
            int x=p[t].top();
            p[t].pop();
            if(x-1>=s[0]){
            x--;
            p[t+1].push(x);
            }
            else
            live++;
        }
        t++;
    }
    printf("%d\n",die);
}


int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        int i,j;
        for(i=0;i<n;i++)scanf("%d",&s[i]);
        sort(s,s+n);
        for(i=0;i<=700;i++)
        while(!p[i].empty())
        p[i].pop();
        for(i=0;i<m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            p[a].push(b);
        }
        gao();
    }
    return 0;
}

解题参考:http://blog.csdn.net/leolin_/article/details/6720249