首页 > 其他分享 >CF 1779C Least Prefix Sum 题解

CF 1779C Least Prefix Sum 题解

时间:2023-01-16 22:33:16浏览次数:69  
标签:int 题解 Sum ans CF mu cal sum 贪心

CF链接:Least Prefix Sum

Luogu链接:Least Prefix Sum


$ {\scr \color {CornflowerBlue}{\text{Solution}}} $

先来解释一下题意:

给定一个数组,问最少把多少个数变成相反数,使得$ \forall \cal{i}$,$ \sum_{k=1}^i a_k$ $ \le$ $ \sum_{k=1}^m a_k$

发现对于所有数据点,$ \cal{n} \le 2 \times 10^5$,说明需要 $ Ο(\cal{n \log n}) $ 或者 $ O(\cal{n}) $的算法。

分析一下题目,发现要分成$ \cal{i} > \cal{m}$ 与$ \cal{i} < \cal{m}$两种情况分类讨论

  • 当 $\cal{i}$ $ > \cal{m}$时:

什么时候才能使$ \sum_{k=1}^i a_k$ $ \le$ $ \sum_{k=1}^m a_k$ 成立呢?

是不是只要使新加的每一段都小于等于0就行了?($ \sum_{k=m}^i a_k$ $ \le$ $ 0$)

也很好证明:一个数($ \sum_{k=1}^m a_k$)加上一个小于等于0的数($ \sum_{k={m+1}}^i a_k$),一定不大于原数。

  • 当 $\cal{i}$ $ < \cal{m}$时:

同理,只要使后加的每一段都小于等于0就行了($ \sum_{k=i}^i a_k$ $ \ge$ $ 0$)

也很好证明:一个数($ \sum_{k=1}^i a_k$)加上一个大于等于0的数($ \sum_{k=i}^m a_k$),一定不小于原数。

而且,由于这两种情况类似(博主太懒),那就只考虑当 $\cal{i}$ $ > \cal{m}$的情况吧。

问题已经转化完了,接下来怎么办?

第一眼想到的是贪心。

设当前要取第$\cal{i}$个。

有一个不成熟的贪心:如果目前累加和加上$a_i$还是小于等于$0$的,就加上$a_i$,如果大于$0$了,就把$a_i$取反,$ ans+1$。

 

Hack数据

5 1
1 -1000 999 2 3

我们只要把999 变成-999就行了,但如果按上面贪心方法,我们要把2,3都改变!

那么贪心就不可以用了吗?

有个神奇的东西交叫反悔贪心!

简单说一下:对于当前不是最优的情况,留到后面重新选择。

我们肯定要让每次改变值后,获得综合最小的值,但当前的选择又不一定最有优。

我们可以用一个优先队列维护,到了每次要改的时候,从优先队列中选出一个收益最大(使目前累加和最大或最小)的值修改。

注意开$ \cal{long long}$并且清空优先队列!

Code(赛时代码,过丑见谅QwQ):

#include<bits/stdc++.h>
#define L long long
using namespace std;
L a[200005];
priority_queue<L,vector<L>,greater<L> > q;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        while(!q.empty()) q.pop();
        int n,m,ans=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        if(n==1)
        {
            printf("0\n");
            continue;
        }
        if(m==1)
        {
            L mu=0;
            for(int i=m+1;i<=n;i++)
            {
                if(a[i]>=0) mu+=a[i];
                else if(a[i]<0 && mu+a[i]>=0)
                {
                    q.push(a[i]);
                    mu+=a[i];
                }
                else
                {
                    ans++;
                    q.push(a[i]);
                    mu+=a[i];
                    mu-=2*q.top();
                    q.pop();
                }
            }
            printf("%d\n",ans);
            continue;
        }
        L mu=0;
        for(int i=m+1;i<=n;i++)
        {
            if(a[i]>=0) mu+=a[i];
            else if(a[i]<0 && mu+a[i]>=0)
            {
                q.push(a[i]);
                mu+=a[i];
            }
            else
            {
                ans++;
                q.push(a[i]);
                mu+=a[i];
                mu-=2*q.top();
                q.pop();
            }
        }
        while(!q.empty()) q.pop();
        mu=0;
        for(int i=m;i>=2;i--)
        {
            if(a[i]<=0) mu+=a[i];
            else if(a[i]>0 && mu+a[i]<=0)
            {
                q.push(-a[i]);
                mu+=a[i];
            }
            else
            {
                ans++;
                q.push(-a[i]);
                mu+=a[i];
                mu+=2*q.top();
                q.pop();
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

 

标签:int,题解,Sum,ans,CF,mu,cal,sum,贪心
From: https://www.cnblogs.com/201929-whx/p/17056454.html

相关文章

  • 洛谷P1496 火烧赤壁【题解】
    事先声明本题解文字比较多,较为详细,算法为离散化和差分,如会的大佬可以移步去别处看这道题的思路(因为作者比较懒,不想新开两个专题)。题目简要给定每个起火部分的起点和终点......
  • ClickHouse(11)ClickHouse合并树MergeTree家族表引擎之SummingMergeTree详细解析
    目录建表语法数据处理汇总的通用规则AggregateFunction列中的汇总嵌套结构数据的处理资料分享参考文章SummingMergeTree引擎继承自MergeTree。区别在于,当合并SummingMerg......
  • CF1775F Laboratory on Pluto - dp - 构造 -
    题目链接:https://codeforces.com/contest/1775/problem/F题解:首先考虑第一问考虑将答案的图形补成一个矩形显然出现凹槽不优,因此可以看成一个矩阵去掉几个角之后的图形......
  • 【问题解决】Tomcat启动服务时提示Filter初始化或销毁出现java.lang.AbstractMethodEr
    问题背景最近在开发项目接口,基于SpringBoot2.6.8,最终部署到外置Tomcat8.5.85下,开发过程中写了一个CookieFilter,实现javax.servlet.Filter接口,代码编译期正常。部署到外......
  • Codeforces Round #844 (Div.1 + Div.2) CF 1782 A~F 题解
    点我看题A.ParallelProjection我们其实是要在这个矩形的边界上找一个点(x,y),使得(a,b)到(x,y)的曼哈顿距离和(f,g)到(x,y)的曼哈顿距离之和最小,求出最小值之后加h就是......
  • Codeforces Round #844 (Div.1 + Div.2) CF 1782 A~F 题解
    点我看题A.ParallelProjection我们其实是要在这个矩形的边界上找一个点(x,y),使得(a,b)到(x,y)的曼哈顿距离和(f,g)到(x,y)的曼哈顿距离之和最小,求出最小值之后加h就是......
  • Codeforces Round #844 (Div.1 + Div.2) CF 1782 A~F 题解
    点我看题A.ParallelProjection我们其实是要在这个矩形的边界上找一个点(x,y),使得(a,b)到(x,y)的曼哈顿距离和(f,g)到(x,y)的曼哈顿距离之和最小,求出最小值之后加h就是......
  • CF1039D You Are Given a Tree
    YouAreGivenaTreeLuoguCF1039DCodeforcesCF1039D题面翻译有一棵\(n\)个节点的树。其中一个简单路径的集合被称为\(k\)合法当且仅当:树的每个节点至多属于其......
  • 电脑维修截图模糊问题解决方案
    微信截图时发现模糊问题可以在两个地方查看设置一、微信应用属性/兼容性中的DPI设置:点击改变高DPI设置,将2、3两处的框选选中,点击ok退出  二、微信中的通用设置:将......
  • 服务器衡量标准--RASUM
    对于一台服务器来讲,服务器的性能设计目标是如何平衡各部分的性能,使整个系统的性能达到最优。如果一台服务器有每秒处理1000个服务请求的能力,但网卡只能接受200个请求,而硬......