Sgu/148

堆维护单调性

//by hza
#include<cstdio>
 
const int MAX=15000+10;
const int INF=(1<<30)-1;
int n;
int w[MAX],l[MAX],p[MAX];
int s[MAX];
 
int less[MAX];
int tree[MAX*2],size=0,tot=0;
 
void swap(int &a,int &b)
{
	int t=a;a=b;b=t;
}
 
void minheap(int now)
{
	int min=0;
	while(1)
	{
		min=now;
		if(now*2<=size&&less[tree[now*2]]<less[tree[min]])
			min=now*2;
		if(now*2+1<=size&&less[tree[now*2+1]]<less[tree[min]])
			min=now*2+1;
		if(now!=min)
		{
			swap(tree[now],tree[min]);
			now=min;
		}
		else break;
	}
}
 
void insert(int a)
{
	tree[++size]=a;
	tot+=p[a];
	int now=size;
	while(now>1 && less[tree[now]] < less[tree[now>>1]] )
	{
		swap(tree[now],tree[now>>1]);
		now>>=1;
	}
}
 
int getmin()
{
	if(size==0)return INF;
	return less[tree[1]];
}
 
void pop()
{
	tot-=p[tree[1]];
	tree[1]=tree[size];
	--size;
	minheap(1);
}
 
int main()
{
	int i,j;
	scanf("%d",&n);
	for(i=1;i<=n;++i)
		scanf("%d %d %d",&l[i],&w[i],&p[i]);
 
	int answer=INF,now=0,sum=0,dead;
	for(i=n;i>=1;--i)
	{
		now=l[i];
		less[i]=w[i]+sum;
		insert(i);
		sum+=l[i];
		while(getmin()-sum<0)
			pop();
		if(tot<answer)
		{
			answer=tot;
			dead=i;
		}
	}
	sum=0;
	for(i=dead;i<=n;++i)
	{
		sum+=l[i];
		if(sum<=w[i])
			printf("%d\n",i);
	}
}

//by abccbazj
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstdlib>
#include <cstring>
#define INF 214748364
using namespace std;
int n;
int w[15100],l[15100],p[15100];
int sum[15100];
int cost;
int ans=INF,ansi;
typedef struct Heap{
    bool operator <(Heap T)const{
        return T.need<need;
    }
    int need;
    int id;
}Heap;
priority_queue<Heap>Q;
int main(){
//    freopen("input.txt","r",stdin);
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d%d%d",&w[i],&l[i],&p[i]);
    }
    for (int i=n;i>0;i--) sum[i]=sum[i+1]+w[i];
    for (int i=n;i>0;i--){
        cost+=p[i];
        while (!Q.empty() && sum[i]-Q.top().need>0){
              cost-=p[Q.top().id];
              Q.pop();
        }
        Heap t;
        t.id=i;
        t.need=l[i]-w[i]+sum[i];
        Q.push(t);
        if (ans>cost){
                      ans=cost;
                      ansi=i;
        }
    }
    cost=0;
    for (int i=ansi;i<=n;i++){
        cost+=w[i];
        if (cost<=l[i]){
                        printf("%d\n",i);
        }
    }
//    while (1);
    return 0;
}