ABC277D 题解

前言

题目传送门！

或许更好的阅读体验？

比较简单的模拟。

思路

首先把 \(a_i\) 排序。每次往后一直跑，如果不能再取了，就停下。

但是这样做是 \(O(n^2)\) 的。我们需要优化。

优化也很容易想到：假设我们跑完了区间 \([l, r]\)，下一个开始的地方其实是 \(r + 1\)。

有了这个优化，时间复杂度就是 \(O(n)\) 了。

实现方面，有一个细节：由于可以取 \((x + 1) \bmod m\)，所以我们跑到末尾时，可能会跳回 \(a_1\)。

为了以防死循环，我们要做两件事：

1. 如果当前回合把全部牌都取光了，要立刻终止。
2. 如果程序已经跳回过 \(1\) 了，取完这一回合后也要立刻终止。

代码

省去了大量的缺省源。

赛时打的，乱糟糟的。

const int N = 2e5 + 5;
int a[N];
void solve()
{
	int n, m;
	scanf("%d%d", &n, &m);
	ll sum = 0;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), sum += a[i];
	sort(a + 1, a + n + 1);
	int pos = 1; ll ans = sum;
	bool calc = false; //是否跳回去过
	for (;;)
	{
		int p = pos; ll tsum = sum;
		for (int nxt; sum != 0;) //nxt 是下一个点
		{
			if (p == n) calc = true; //即将跳回去
			nxt = (p == n ? 1 : p + 1);
			sum -= a[p];
			if (a[p] != a[nxt] && (a[p] + 1) % m != a[nxt]) break;
			p = nxt;
		}
		ans = min(ans, sum);
		if (calc) break;
 
		if (p == n) calc = true; //即将跳回去
		pos = (p == n ? 1 : p + 1);
		sum = tsum;
	}
	cout << ans << '\n';
}

希望能帮助到大家！

原文地址：http://www.cnblogs.com/liangbowen/p/16885477.html