I_Stock

• 2015 acm-icpc 예선
• Problem I Stock

전체에서 가장 큰 수는 가장 비싸게 팔아야 할 가격이므로

이전의 모든 물건들은 큰 값으로 팝니다.

뒤에 물건이 남아있다면 나머지 배열을 기준으로 반복하여 구합니다.

int Stock[1000001];
int n;

int f(int src, int des)
{
	int Big = -1;
	int BigIndex;
	for (int i = src; i <= des; i++)
	if (Big < Stock[i])
	{
		Big = Stock[i];
		BigIndex = i;
	}

	return BigIndex;
}
int g(int src, int des)
{
	int StockValue = Stock[des];
	int V = 0;
	for (int i = src; i < des; i++)
		V += StockValue - Stock[i];

	return V;
}
int main()
{
	int T;
	for (scanf("%d", &T); T--;)
	{
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
			scanf("%d", &Stock[i]);

		int src = 0, des = n - 1;
		int R = 0;
		while (1)
		{
			int _des = f(src, des);
			R += g(src, _des);
			if (_des == 0 || _des == des)
				break;
			src = _des + 1;
		}
		printf("%d\n", R);
	}
	return 0;
}