SGU 148 堆优化+模拟 or 平衡树

题意：

有一个大水桶，里面有N层。从上至下标为1、2、3…层。

如果破坏某一层（需要一定代价），那么水就会流到下一层。

另外，如果某一层的水量超过了他能负荷的水量。也会自动爆炸。。。水就会自动流到下一层。

现在你是恐怖分子，求怎样花费最少，可以破坏掉第N层。

分析：

首先水不可能是断流的。因为这样上面一层就没有任何意义了。

所以我们可以枚举水开始下流在哪一层。如果中间遇到水量不够自动破坏，就需要破坏掉这一层（即付出相应花费）。

这样到达每一个层的水量就是sum(i,j)其中i为开始流的层，j表示当前层。

我们发现这满足单调性。我们把i从N枚举到1。再用堆or平衡树维护即可。

因为i减1不会破坏他们的大小关系。

code:

#include #include using namespace std;
const int N=20000;
const int INF=0x7FFFFFFF;
struct headtype{int limit,w,p,i;} heap[100000];
int n,tot=0,water[N],limit[N],p[N],Swater=0,outtime[N];

void init(){
     scanf("%d",&n);
     for (int i=1;i<=n;i++)
       scanf("%d%d%d",&water[i],&limit[i],&p[i]);
}

inline int f(int t){
       return (heap[t].limit-heap[t].w);
}

void up(int k){
     while (k>1 && f(k/2)>f(k)){
           swap(heap[k],heap[k/2]);
           k/=2;
     }
}

void down(int k){
     while (k*2<=tot){
           int t;
           if (k*2+1<=tot && f(k*2+1)                                         else t=k*2;
           if (f(t)           k=t;
     }
}

void ins(int W,int L,int P,int i){
     tot++;
     heap[tot].w=W;
     heap[tot].limit=L;
     heap[tot].p=P;
     heap[tot].i=i;
     up(tot);
}

void del(){
     heap[1]=heap[tot];
     tot–;
     down(1);
}

void work(){
     int ans=INF,now=0,ansi=0;
     for (int i=n;i>=1;i–){
         Swater+=water[i];
         now+=p[i];
         ins(water[i]-Swater,limit[i],p[i],i);
         while (tot>0 && heap[1].w+Swater>heap[1].limit){
               now-=heap[1].p;
               outtime[heap[1].i]=i;
               del();
         }
         if (now           ans=now;
           ansi=i;
         }
     }
     for (int i=ansi;i<=n;i++)
       if (outtime[i]}

int main(){
    init();
    work();
}