2018年ACM-ICPCアジア青島地区競技-J:Books

http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5837
Time Limit: 1 Second      Memory Limit: 65536 KB
Problem solving report:
Description:n本でm本を買う、買うルールは以下の通りです:左から右へn本をスキャンし、現在の財布の中のお金が本の値段より大きい場合は、買って(買わなければならない)、最大いくら持っていけるかを聞いて、お金の数は非負の整数でなければなりません.もし案がなければ、Impossibleに負けて、無限のお金を持っていけば、Richmanを出力します.
Problem solving:欲張り

先数は全部で何個の0(0は買わなければならない)があって、ans個を仮定して、ans>mならば、方案がなくて、impossibleを出力します;

それから残りのn-ansの本の中で前のm-ansの本を買って、お金を得てsumを数えます;

残りの最小値を求めると、最大持参可能なお金はsum+min-1である.

n nがmと等しい場合、無限のお金を持ってRichmanを出力することができる.

#include 
int a[100010];
int main()
{
	long long sum;
	int t, x, k, n, m, ans, minn;
	scanf("%d", &t);
	while (t--)
	{
		minn = 1e9;
		sum = ans = k = 0;
		scanf("%d%d", &n, &m);
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &a[k]);
			if (!a[k])
				ans++;
			else k++;
		}
		if (ans > m)
			printf("Impossible
");
		else if (n == m)
			printf("Richman
");
		else
		{
			m -= ans;
			for (int i = 0; i < m; i++)
				sum += a[i];
			for (int i = m; i < k; i++)
				if (a[i] < minn)
					minn = a[i];
			printf("%lld
", sum + minn - 1);
		}
	}
	return 0;
}