2011-0049

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

这个题的意思是关羽哥依次要过n个关卡，在过每个关卡的时候会扣一定数量的血Xi，每次打过一个关卡可以选择在该关卡回血，回血速度是Vi/天。关羽血有个上限Max，而且只能在当前关卡加血。
最后问你至少需要几天才能冲过全部关卡。
这个比较直观的可以想到贪心，如果需要加血，就尽可能挑实际回血速度最大的关卡加血。只不过在贪心的过程中需要注意的是关羽的血量是不能超过Max的，这导致有时关卡虽然Vi较大，但实际回血效果很小。
我用的一个优先队列才实现贪心，通过3个变量来维护这个优先队列。
先计算不加血经过每个关卡时，关羽的血量Ai。
用added表示当前已经加的血量，d表示当前加血的天数，pos标记有效关卡的起点。
Ai+added就是经过每个关卡时的实际血量了。
从头遍历，一旦需要回血，就pop出当前经过的所有关卡中，回血速度最大且在有效区间的。
判断其实际回血效果，一旦实际回血效果小于Vi的话，就更新Vi和pos。
若实际效果和Vi相同，就选择在该关卡休息。
{{{
#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;

struct node{
    int v,id;
    bool operator < (const node &tn) const{
            return v<tn.v;
    }
};

priority_queue<node> pq;
long long a[100005];

int main(){
    int i,j,k,x,pos,n;
    long long t,t2,added,max,d;
    node nd1,nd2;
    while(scanf("%d%lld",&n,&max)==2){
        a[0]=max;   d=added=0;  pos=0;
        for(i=1;i<=n;i++){
            scanf("%d%d",&x,&nd1.v);
            nd1.id=i;
            a[i]=a[i-1]-x;
            t=-a[i]-added+1;  //需要回血的量
            if(t>0){
                while(1){
                    t=-a[i]-added+1;
                    nd2=pq.top();
                    if(nd2.id<pos){pq.pop(); continue;}
                    if(t%nd2.v==0)  t2=t/nd2.v;
                    else    t2=t/nd2.v+1;
                    if((max-a[nd2.id]-added)/nd2.v>=t2){  //Vi等于实际效果
                        added+=t2*nd2.v;    d+=t2;  break;
                    }
                    else{  //Vi小于实际效果
                        t=(max-a[nd2.id]-added)/nd2.v;
                        pq.pop();
                        added+=t*nd2.v;
                        d+=t;
                        pos=nd2.id;
                        nd2.v=max-a[nd2.id]-added;
                        pq.push(nd2);
                    }
                }
            }
            pq.push(nd1);
        }
        while(!pq.empty()){pq.pop();}
        printf("%lld\n",d);
    }
}
}}}
By riversouther

这个题的意思是关羽哥依次要过n个关卡，在过每个关卡的时候会扣一定数量的血Xi，每次打过一个关卡可以选择在该关卡回血，回血速度是Vi/天。关羽血有个上限Max，而且只能在当前关卡加血。

最后问你至少需要几天才能冲过全部关卡。

这个比较直观的可以想到贪心，如果需要加血，就尽可能挑实际回血速度最大的关卡加血。只不过在贪心的过程中需要注意的是关羽的血量是不能超过Max的，这导致有时关卡虽然Vi较大，但实际回血效果很小。

我用的一个优先队列才实现贪心，通过3个变量来维护这个优先队列。

先计算不加血经过每个关卡时，关羽的血量Ai。

用added表示当前已经加的血量，d表示当前加血的天数，pos标记有效关卡的起点。

Ai+added就是经过每个关卡时的实际血量了。

从头遍历，一旦需要回血，就pop出当前经过的所有关卡中，回血速度最大且在有效区间的。

判断其实际回血效果，一旦实际回血效果小于Vi的话，就更新Vi和pos。

若实际效果和Vi相同，就选择在该关卡休息。

#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;
struct node{
    int v,id;
    bool operator < (const node &tn) const{
            return v<tn.v;
    }
};
priority_queue<node> pq;
long long a[100005];
int main(){
    int i,j,k,x,pos,n;
    long long t,t2,added,max,d;
    node nd1,nd2;
    while(scanf("%d%lld",&n,&max)==2){
        a[0]=max;   d=added=0;  pos=0;
        for(i=1;i<=n;i++){
            scanf("%d%d",&x,&nd1.v);
            nd1.id=i;
            a[i]=a[i-1]-x;
            t=-a[i]-added+1;  //需要回血的量
            if(t>0){
                while(1){
                    t=-a[i]-added+1;
                    nd2=pq.top();
                    if(nd2.id<pos){pq.pop(); continue;}
                    if(t%nd2.v==0)  t2=t/nd2.v;
                    else    t2=t/nd2.v+1;
                    if((max-a[nd2.id]-added)/nd2.v>=t2){  //Vi等于实际效果
                        added+=t2*nd2.v;    d+=t2;  break;
                    }
                    else{  //Vi小于实际效果
                        t=(max-a[nd2.id]-added)/nd2.v;
                        pq.pop();
                        added+=t*nd2.v;
                        d+=t;
                        pos=nd2.id;
                        nd2.v=max-a[nd2.id]-added;
                        pq.push(nd2);
                    }
                }
            }
            pq.push(nd1);
        }
        while(!pq.empty()){pq.pop();}
        printf("%lld\n",d);
    }
}

By riversouther