自动搬运

查看原文

来自洛谷，原作者为

	GI录像机 除了OI，除了这个世界，我还是剩点东西的

搬运于2025-08-24 22:30:52，当前版本为作者最后更新于2022-09-14 13:03:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

对答案有影响的只有两个因素：颜色数与玩具数。考虑从右往左枚举左端点，再枚举颜色数。由于要求最小值，在颜色数一定时，应该尽可能让玩具数更大。我们可以记录每个字母上一次出现的位置，记为 $las_i$。将 $las$ 数组排序，$las_i-1$ 就是只有 $i-1$ 个颜色时，使玩具数最多的右端点。

为了避免浮点误差，我们可以通过移项判断大小。

代码：

#include<bits/stdc++.h>
using namespace std;
int n, ansc = 1, ansn = 1, l = 1, r = 1;
string s;
struct Node {
	int las, id;
} a[30];
bool cmp1(Node x, Node y) {
	return x.las < y.las;
}
bool cmp2(Node x, Node y) {
	return x.id < y.id;
}
int main() {
	//freopen("toy.in", "r", stdin);
	//freopen("toy.out", "w", stdout);
	cin >> n >> s;
	for (int i = 0; i <= 26; i++) {
		a[i].id = i;
		a[i].las = 0x3f3f3f3f;
	}
	for (int i = n - 1; i >= 0; i--) {
		a[s[i] - 'a'].las = i;
		sort(a, a + 26, cmp1);
		for (int j = 1; j <= 26; j++) {
			if (a[j].las == 0x3f3f3f3f){
				if (j * ansn < ansc * (n - i)) {
					r = n;
					l = i + 1;
					ansn = r - l + 1;
					ansc = j;
				}
				break;
			}
			if (j * ansn < ansc * (a[j].las - i)) {
				r = a[j].las;
				l = i + 1;
				ansn = r - l + 1;
				ansc = j;
			}
		}
		sort(a, a + 26, cmp2);
	}
	cout << l << " " << r << endl;
	return 0;
}