首页 > 代码库 > poj3465（贪心+优先队列）

poj3465（贪心+优先队列）

2024-07-26 22:09:51   218人阅读

Battle
Time Limit: 2000MS Memory Limit: 131072K
Total Submissions: 1851 Accepted: 455

Description

You‘re Zhu Rengong, a formidable hero. After a number of challenging missions, you are finally facing the final Boss – a black dragon called Heilong. Due to his overwhelming power, you have to plan your actions carefully.

You have H1 hit points (HP) at the beginning of the battle, and Heilong has H2. Heilong attacks you each time you do an action, and deal Ai points of damage in the i-th round. You have three kinds of actions.

  • Attack. You attack Heilong, and do x points of damage.
  • Defend. You focus on avoiding the attack of Heilong. This action nullifies Heilong‘s attack in this round.
  • Heal. You heal yourself, adding y hit points to yourself. There is no upper bound on your HP.

If anyone‘s HP drop below or equal to 0, he dies. If you can‘t kill the dragon within N rounds, you will also die. So you need to know how many rounds you need to kill the black dragon. If you cannot kill him, you will have to calculate the maximal damage you can do on Heilong.

Input

The first line contains five integers, N, x, y, H1, H2. 1 ≤ N ≤ 105, 1 ≤ x,y ≤ 104, 1 ≤ H1,H2 ≤ 109. Then follow N lines, the ith line contains one integer Ai-1. 1 ≤ Ai-1 ≤ 104.

Output

If you can kill Heilong, the first line of your output should be "Win". Otherwise "Lose".
The second line contains the number of rounds you need to kill Heilong if the first line is "Win", or the maximal damage you can do if the first line is "Lose".

Sample Input

Sample Input 1
4 1 1 3 3
1
10
1
10
Sample Input 2
4 1 1000 1 4
1
10
1
1

Sample Output

Sample Output 1
Win
4
Sample Output 2
Lose
3

Hint

In Sample 1, you have to defend in the 2nd round, othewise you will die. 
In Sample 2, you heal yourself in the first round, and keep attacking until N rounds expires.

Source

POJ Monthly--2007.11.25, Yang Yi
题目的意思是zhurengong打heilong,zhurengong有h1血,heilong有h2血，zhurengong的伤害是固定的，而heilong的伤害是不固定的。
zhurengong可以选择攻击，防御，补血，注意的是防御不掉血，攻击和补血会掉血。
采取的是贪心策略，次次都打，死了之后，再回溯放弃那次最痛的直到没死。

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int a[123456];
int main()
{
    int n,x,y,me,hl;
    int i;
    while(scanf("%d%d%d%d%d",&n,&x,&y,&me,&hl)!=EOF){
        priority_queue<int> pq;
        int hit=0,mhit=0;
        for(i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(i=1;i<=n;i++){
            hit++;
            mhit=max(hit,mhit);
            if(hit*x>=hl)break;
            me-=a[i];
            pq.push(max(a[i],y));
            //cout<<me<<" "<<hl<<endl;
            while(me<=0&&!pq.empty()){
                int j=pq.top();
                pq.pop();
                me+=j;
                hit--;

            }
        }
        if(i<=n){
            cout<<"Win"<<endl;
            cout<<i<<endl;

        }else{
            cout<<"Lose"<<endl;
            cout<<mhit*x<<endl;

        }
    }

    return 0;
}


poj3465（贪心+优先队列）


联系
我们