欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

CF1082E Increasing Frequency

程序员文章站 2024-03-19 09:33:40
...

\(\color{#0066ff}{ 题目描述 }\)

给你一个长度为 \(n\) 的数列 \(a\) ,你可以任意选择一个区间 \([l,r]\), 并给区间每个数加上一个整数 \(k\), 求这样一次操作后数列中最多有多少个数等于 \(c\)

\(\color{#0066ff}{输入格式}\)

第一行两个整数 \(n\), \(c\) . 第二行 \(n\) 个整数 \(a_1,a_2,...,a_n\).

\(\color{#0066ff}{输出格式}\)

输出一个整数表示答案。

\(\color{#0066ff}{输入样例}\)

6 9
9 9 9 9 9 9
    
    
    
3 2
6 2 6

\(\color{#0066ff}{输出样例}\)

6

    
2

\(\color{#0066ff}{数据范围与提示}\)

\(1\le n,c,a_i \le 5\cdot 10^5\).

\(\color{#0066ff}{ 题解 }\)

考虑暴力,枚举区间左右端点

当前的答案为区间内出现最多的数的个数+区间外c的个数

对于区间外c的个数,可以用前缀后缀和来维护

现在考虑区间维护

可以发现,离散化后的数最多n个

既然不知道区间出现最多的数的次数

就考虑枚举值域,强制让其为次数最多的数,开vector记录出现的位置

上面的强制是不会影响答案的(因为一定会找到最优情况)

对于枚举的每个位置,考虑\(ans = x + y + r - l + 1\)

x是l前面c的个数(前缀和维护),y是r后面c的个数(后缀和维护)

(r - l + 1)是出现次数,因为我们用vector存了它出现的位置,所以直接vector下标作差就是出现次数

\(ans = (x -l) + (r+y+1)\)

要使ans最大, 则两边都最大,而且左边只与l有关,右边只与r有关

我们枚举l的时候,左边的值是固定的,然后对于右边的值,开个变量维护一下max就行

因为总共就n个位置,所以复杂度\(O(n)\)

#include<bits/stdc++.h>
#define LL long long
LL in() {
    char ch; LL x = 0, f = 1;
    while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
    for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
    return x * f;
}
const int maxn = 5e5 + 100;
int n, c, a[maxn], b[maxn];
int l[maxn], r[maxn], dp[maxn];
std::vector<int> v[maxn];
int main() {
    n = in(), c = in();
    for(int i = 1; i <= n; i++) a[i] = b[i] = in();
    b[n + 1] = c;
    std::sort(b + 1, b + n + 2);
    int len = 1;
    for(int i = 2; i <= n + 1; i++) if(b[i] != b[i - 1]) b[++len] = b[i];
    for(int i = 1; i <= n; i++) a[i] = std::lower_bound(b + 1, b + len + 1, a[i]) - b;
    c = std::lower_bound(b + 1, b + len + 1, c) - b;
    for(int i = 1; i <= n; i++) l[i] = l[i - 1] + (a[i] == c);
    for(int i = n; i >= 1; i--) r[i] = r[i + 1] + (a[i] == c);
    for(int i = 1; i <= n; i++) v[a[i]].push_back(i);
    for(int i = 1; i <= len; i++) {
        int max = -maxn;
        for(int j = (int)v[i].size() - 1; j >= 0; j--) {
            max = std::max(max, r[v[i][j] + 1] + 1 + j);
            dp[i] = std::max(dp[i], max + l[v[i][j] - 1] - j);
        }
    }
    int ans = 0;
    for(int i = 1; i <= len; i++) ans = std::max(ans, dp[i]);
    printf("%d\n", ans);
    return 0;
}
/*x + y + j - i + 1 = (x - i) + (y + j + 1) */

上一篇: day3 总结

下一篇: MD5算法小应用