P1599 结算日

一、题目描述

“不放债不借债”，贝西多么希望自己可以遵循这个忠告。她已经和她的 N(1≤N≤100,000) 个朋友有了债务关系，或者借债了，或者放债了。她的 N 个朋友依次标号为 1…N。

结算日终于来临了。她知道，朋友欠她的钱比她欠朋友的钱多。她的朋友们分布在一条直线上，第 i 头奶牛站的位置距离谷仓 i 米。贝西打算沿着这条直线行走，从欠她钱的奶牛手里收钱回来，并且还钱给她欠钱的奶牛。

当她沿直线移动的时候，她可以要求任何欠她钱的奶牛还全部的钱。当她有足够的钱可以还清她的某个债，就可以把钱给对应的奶牛还清她的债。奶牛 i 欠贝西 $D i$元 $(−1,000≤D i≤1,000,D i=0)$，负数表示贝西欠奶牛 i 钱。

贝西从谷仓出发，位置为 0，初始贝西没有钱。贝西收回她的所有借债，并且还清她的欠债所需行走的最短距离是多少？

注意：她必须在最后一头奶牛所在的位置，完成她的行走。$$

二、题目思路

1、核心观察

债务结算的顺序会影响行走距离，而最优策略需满足：

对于负债（D_i < 0），必须在到达该位置前积累足够的资金（通过收取之前的债权）行走路径应尽量减少往返，优先按坐标顺序处理，仅在必要时折返

2、算法设计

采用贪心策略：

从左到右（坐标 0→N）遍历所有位置记录当前资金余额，遇到债权（D_i > 0）立即收取，增加余额遇到债务（D_i < 0）时，若当前余额足够则直接偿还；若不足，需计算需要折返到右侧收取的最小债权金额，确保能偿还当前债务

3、距离计算

基础距离：从 0 到 N 的直线距离 N（必须走）额外距离：因折返收取债权产生的往返距离（每次折返会增加 2× 折返距离）

三、正确代码

#include<bits/stdc++.h>
using namespace std;

int sum,last=-1;//sum代表贝西手上的钱数，last代表第一个收债人的位置。
int a[100005];
int main()
{	
	int n;
	cin>>n;
	int ans=n;//ans代表所需要行走的最短距离。(单位为米)
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		sum+=a[i];
		if(sum>=0&&last!=-1){
			ans+=2*(i-last);
			last=-1;
		}else if(sum<0&&last==-1){
			last=i;
		}
	}
	cout<<ans;
	return 0;
}