记录编号	293068	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1363.水站	最终得分	100
用户昵称	kito	是否通过	通过
代码语言	C++	运行时间	0.118 s
提交时间	2016-08-09 17:48:46	内存使用	0.69 MiB

#include<cstdio>
using namespace std;
#define fcl fclose(stdin);	fclose(stdout);	return 0
int n;
int W[15010]={0},L[15010]={0},P[15010]={0};
int Nw[15010]={0},Place[15010]={0}; 

int GetPlace(int i){
	if(i==13){}
	int l=0,r=i-1,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(Nw[i]-Nw[mid]>L[i])	l=mid+1;
		else r=mid-1;
	}
	return l+1;
}

int kito[15010]={0};
void Archer1(int a,int k){
	for(int i=a;i<=n;i+=(i&(-i))){
		kito[i]+=k;
	}
}
int Saber1(int a){
	int tot=0;
	for(int i=a;i>=1;i-=(i&(-i))){
		tot+=kito[i];
	}
	return tot;
}

int alice[15010]={0};
void Archer2(int a,int k){
	for(int i=a;i<=n;i+=(i&(-i))){
		alice[i]+=k;
	}
}
int Saber2(int a){
	int tot=0;
	for(int i=a;i>=1;i-=(i&(-i))){
		tot+=alice[i];
	}
	return -tot;
}

int main(){
	freopen("station.in","r",stdin);
	freopen("station.out","w",stdout);
	
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d%d%d",&W[i],&L[i],&P[i]);
		Nw[i]=Nw[i-1]+W[i];//求水量的前缀和 
	}
	int x;
	/*
		如果某一个水站能从上面的水站获得水，证明上面的水站一定减压（但不一定是手动减压）
		为了使n减压，我是为了让n获得水，也就是说，我最高的减压水站的水要能进入n水站。也就是说，
	从最高的减压水站开始到n都要减压。
		为了节省资金，应该是让水站尽可能自动开闸。
		如果i是最高的减压水站，那么下面的每个水站获得的水量都是固定且已知的。
		j水站上面开闸的水站越多，就越可能不花钱开闸。
		我们可以二分求得，第j水站必须花钱开闸时，最高的水站的最高位置。
		这就是GetPlace函数。 
	*/ 
	for(int i=1;i<=n;++i){
		x=GetPlace(i);//求得第i个水站必须手动减压时，最高的开始位置。 
		Place[i]=x;
		Archer1(x,P[i]);//利用树状数组。 
		Archer2(i+1,P[i]);// 从x到i+1需要花i的钱手动开闸。 
	}
	int Minn=0x7fffffff,a,Ans;
	for(int i=1;i<=n;++i){
		a=Saber1(i)+Saber2(i);
		if(a<Minn){
			Minn=a;
			Ans=i;
		}
	}
	printf("%d\n",Minn);
	for(int i=Ans;i<=n;++i){
		if(Place[i]<=Ans)	printf("%d ",i);//如果必须花钱的位置的起始位置在Ans之外，就要花钱。 
	}
	fcl;
}