题解 P7544 [COCI2019-2020#4]Nivelle

GI录像机 · 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;
}