首页 > 代码库 > poj1827A Bunch Of Monsters(贪心)

poj1827A Bunch Of Monsters(贪心)

2024-07-16 09:40:34   219人阅读

题目链接：

啊哈哈，点我点我

题目意思：

给出n个怪物可以拿到卡片的范围和这个怪物对主人公造成的伤害。。然后求最后得到怪物对主人公的最小伤害。。

思路：对怪物造成的伤害从大到小排序，然后对n个怪物进行逐一枚举，枚举时对它的时间进行逆向枚举，然后没有被访问到的将其伤害降为0，最后统计一下即可。

题目：

A Bunch Of Monsters
Time Limit: 2000MS Memory Limit: 30000K
Total Submissions: 938 Accepted: 354

Description

Background 
Jim is a brave explorer. One day, he set out for his next destination, a mysterious hill. When he arrived at the foot of the hill, he was told that there were a bunch of monsters living in that hill, and was dissuaded from continuing his trip by the residents near the hill. Nevertheless, our Jim was so brave that he would never think of giving up his exploration. 
The monsters do exist! When he got into that hill, he was caught by a bunch of fearful monsters. 
Fortunately, the monsters didn’t plan to kill him or eat him for they were planning a big party. They wanted to invite Jim, a clever human being, to their party, in order to let human beings know that the monsters also have wonderful parties. 
Problem 
At the end of the party, the monsters promised that, after the last game, they would set Jim free. The game is described as follow: 
1. There are a great many boxes of treasure, which are numbered from 1 to X. One box has the only one number; one number can only appear on one box. Furthermore, we can assume that X is INFINITY, because the monsters have got a lot of treasure from the men they caught. 
2. There are N monsters in this game. Each picks up a card randomly. After that, he / she (it?) opens it, getting a positive integer number d[i], and cannot change it or pick up another card again. The range of d[i] is from 1 to M. If the i-th monster get the number d[i], he can only get the treasure box numbered equal to or less than d[i]. What’s more, one box only can be distributed to one monster; one monster can only get one box. 
3. Of course, there are many ways to distribute the boxes to the monsters when N monsters get their numbers; and not every monster can get a box in many cases. Jim has the right to make the arrangement; however, he also knows that the monsters that don’t get the boxes will also punish him. 
Jim knows the strength of the N monsters. The i-th one has the strength s[i]. We call the sum of strength s[i] of all the monsters that don’t get the boxes --- the DAMAGE to Jim. Your task is to help Jim find out the minimum DAMAGE to him. 

Input

The input consists of several test cases. In the first line of each test case, there are two positive integers N and M (1<=N<=50000, 1<=M<=50000), indicating the number of monsters and the range of numbers the monsters possibly get on the cards. Then there are N integers d[i] (1<=d[i]<=M) in the following lines, which are the numbers those monsters got. And in the rest lines of one test case, there are other N positive integers s[i] (1<=s[i]<=20000), indicating the strength of each monsters. The test case starting with 2 zeros is the final test case and has no output.

Output

For each test case, print your answer, the minimum DAMAGE, in one line without any redundant spaces.

Sample Input

1 1
1
1
7 7
6 4 4 2 3 4 3
10 70 20 60 30 50 40
0 0

Sample Output

0
50

Source

Atlas of rruucc@POJ


代码为：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=50000+10;
int vis[maxn];

struct Damage
{
    int time,val;
}damage[maxn];

bool cmp(Damage a,Damage b)
{
    if(a.val==b.val)
        return a.time>b.time;
    else
        return a.val>b.val;
}

int main()
{
    int n,m;
    __int64 ans;
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0)  return 0;
        ans=0;
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
            scanf("%d",&damage[i].time);
        for(int i=1;i<=n;i++)
            scanf("%d",&damage[i].val);
        sort(damage+1,damage+1+n,cmp);
        for(int i=1;i<=n;i++)
        {
            int temp=damage[i].time;
            for(int j=temp;j>=1;j--)
            {
                if(!vis[j])
                {
                    damage[i].val=0;
                    vis[j]=1;
                    break;
                }
            }
        }
        for(int i=1;i<=n;i++)
            ans=ans+damage[i].val;
        printf("%I64d\n",ans);
    }
    return 0;
}



联系
我们