pku2940.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 73 行

#include <stdio.h>
#define SIZE 100001

typedef struct Node
{
	int v;
	int id;
}Node;

typedef long long llong;

Node A[SIZE], B[SIZE];
int Al, Bl;
int N;

int abs(int x){return x > 0 ? x : -x;}

void Solve()
{
	int i, val, j;
	Al = 0;
	Bl = 0;
	llong ans = 0, tmp;
	for (i = 0; i < N; i++)
	{
		scanf("%d", &val);
		if (val > 0)
		{
			A[Al].v = val;
			A[Al].id = i;
			Al++;
		}
		else
		{
			B[Bl].v = -val;
			B[Bl].id = i;
			Bl++;
		}
	}
	j = 0;
	for (i = 0; i < Al; i++)
	{
		while (A[i].v > 0)
		{
			if (B[j].v <= A[i].v)
			{
				tmp = B[j].v * abs(A[i].id - B[j].id);
				ans += tmp;
				A[i].v -= B[j].v;
				B[j].v = 0;
				j++;
			}
			else
			{
				tmp = A[i].v * abs(A[i].id - B[j].id);
				ans += tmp;
				B[j].v -= A[i].v;
				A[i].v = 0;
				break;
			}
		}
	}
	printf("%I64d\n", ans);
}

int main()
{
	while (EOF != scanf("%d", &N) && N)
		Solve();
	return 0;
}