【前缀和+反悔贪心】Hello2023 C. Least Prefix Sum

小鱼儿 2024-03-22 15:30 21阅读 0赞

[Problem - C - Codeforces][]

![d309b559500a4574b44f668e2ca20c68.png][]

思路：

![fd47ac5587ad45d6b143b907846bd9ee.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int mod=998244353;
    
    int N,M;
    int a[mxn];
    
    void solve(){
    	cin>>N>>M;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	int sum=0,ans=0;
    	multiset<int> S;
    	for(int i=M+1;i<=N;i++){
    		sum+=a[i];
    		S.insert(a[i]);
    		if(sum<0){
    			int mi=*S.begin();
    			sum-=2*mi;
    			ans++;
    			S.erase(S.begin());
    		}
    	}
    	sum=0;
    	S.clear();
    	for(int i=M;i>=2;i--){
    		sum+=a[i];
    		S.insert(a[i]);
    		if(sum>0){
    			int mx=*prev(S.end());
    			sum-=2*mx;
    			ans++;
    			S.erase(prev(S.end()));
    		}
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1779/problem/C
[d309b559500a4574b44f668e2ca20c68.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/4e617edf23ff4302b9e831a50ad049cc.png
[fd47ac5587ad45d6b143b907846bd9ee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/9a5179f4b8bd43c2a6ea1875726152a6.png

发表评论取消回复

表情：

评论列表（有 0 条评论，21人围观）

还没有评论，来说两句吧...

相关阅读

相关【反悔贪心】CF1278B CF11B

[Problem - 1278B - Codeforces][] 题意： ![c0fbd2f3d4224469b8dd5bb7d049f4ee.png][] 思路： !

以你之姓@/ 2024年03月24日 18:30/ 0 赞/ 144 阅读

相关【前缀和+反悔贪心】Hello2023 C. Least Prefix Sum

[Problem - C - Codeforces][] ![d309b559500a4574b44f668e2ca20c68.png][] 思路： ![fd47ac55

小鱼儿/ 2024年03月22日 15:30/ 0 赞/ 22 阅读

相关【贪心（计算贡献）+操作】CF833div2 C. Zero-Sum Prefixes

这道题考虑贪心，计算贡献就好了 [Problem - C - Codeforces][] 题意：定义一个数列的值为前缀和为0的位置个数，每次操作可以把一个ai==0的数

àì夳堔傛蜴生んèń/ 2024年03月22日 06:06/ 0 赞/ 87 阅读

相关【反悔贪心】2022ICPC南京 G

[Problem - G - Codeforces][] 题意 ![d90998478af246c99ef1811cc2a9b959.png][] 思路首先容易发现，

港控/mmm°/ 2024年02月21日 11:58/ 0 赞/ 101 阅读

相关反悔贪心 + 优先队列：PIPI的逃跑路线Ⅳ

反悔贪心 + 优先队列：PIPI的逃跑路线Ⅳ 文章目录反悔贪心 + 优先队列：PIPI的逃跑路线Ⅳ 问题：思路：

﹏ヽ暗。殇╰゛Y/ 2023年10月06日 20:26/ 0 赞/ 51 阅读

相关 208. Implement Trie (Prefix Tree)（前缀树)

Implement a trie with insert, search, and startsWith methods. Example: Trie trie = n

た入场券/ 2023年07月25日 06:14/ 0 赞/ 23 阅读

相关前缀列表---Prefix-List

在谈起前缀列表之前，我们首先简单的分析一下常用的抓取路由的ACL(访问控制列表)的作用:1.抓数据2.抓路由。举个简单的例子来看一看: 1.标准ACL: R1(co

矫情吗；*/ 2022年09月11日 07:09/ 0 赞/ 189 阅读

相关 Implement Trie (Prefix Tree)（C++实现 Trie (前缀树)）

（1）多个子节点 class Trie { private: vector<Trie> v; bool isend;

雨点打透心脏的1/2处/ 2022年09月02日 00:47/ 0 赞/ 197 阅读

相关 D. Least Cost Bracket Sequence （贪心）

[点击打开链接][Link 1] http://codeforces.com/contest/3/problem/D D. Least Cost Bracket

妖狐艹你老母/ 2022年06月18日 09:07/ 0 赞/ 165 阅读

相关 SpringMVC--视图解析器概述和前缀prefix、后缀suffix

Spring MVC视图解析器配置 Spring 视图解析器是 Spring MVC 中的重要组成部分，用户可以在配置文件中定义 Spring MVC 的一个视图解析器（

待我称王封你为后i/ 2021年08月13日 13:16/ 0 赞/ 476 阅读