Codeforces Round 922 (Div. 2)

Blocking Elements

算法本质

思维、二分、dp

题目大意（改）

给定长度n数组a[]，玩家可以选择任意个元素涂成黑色：

• res1值为将所有黑色元素值之和
• 2个相近黑色元素之间的元素（不含黑色元素）为一组，剩余的若干组，其中元素和最大值计为res2值

输出最小化的max(res1, res2)值。

n <= 1e5

思路推演

通常来说，这样的“最小化最大值”和“最大化最小值”的题目，我们可以首先尝试一下二分思路，其可以在增加log复杂度情况下多提供一个条件。

当我们获取到当前回合的上限值时，有2个目标：

• 每组元素和 < 上限值
• 选择元素和 < 上限值

用贪心的思路去想的话，会发现情景十分复杂，很难获取最优解。
所以转变思路使用dp去处理。

dp条件十分明显，dp[x]=y可以表示对于1~x来说，x必涂黑的情况下已经涂黑元素和值为y。
因为有2个目标，所以肯定是需要维护一个、力求保证另一个，这里我们选择维护每组元素和，最后检查选择元素和。

可以使用优先队列来解决，代码相对简洁，不懂可以看一下代码。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn], dp[maxn], pre[maxn];
inline void solve()
{
    cin>>n;
    for (int i=1; i<=n; i++)    cin>>a[i], pre[i]=pre[i-1]+a[i];
    a[n+1] = 0;        // 为了方便就直接使用dp[n+1]，其需要保证a[n+1]为0
    int l=1, r=1e13;
    int ans=r;
    while (l<=r)
    {
        int mid=(l+r)/2;
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
        q.push({0, 0});        // {val, idx}
        for (int i=1; i<=n+1; i++)
        {
            while (q.size() && pre[i-1] - pre[q.top().second] > mid)    // 保证中间
                q.pop();
            dp[i] = a[i] + q.top().first;
            q.push({dp[i], i});
        }
        if (dp[n+1]<=mid)
        {
            r=mid-1;
            ans=mid;
        }
        else
            l=mid+1;
    }
    cout<<ans<<endl;
    return;
}

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。