賽後補題:Hello 2023 CF1779C. Least Prefix Sum

傳送門:CF

題目描述:

題目Latex過多,此處省略
輸入:
6
4 3
-1 -2 -3 -4
4 3
1 2 3 4
1 1
1
5 5
-2 3 -5 1 -20
5 2
-2 3 -5 -5 -20
10 4
345875723 -48 384678321 -375635768 -35867853 -35863586 -358683842 -81725678 38576 -357865873
輸出:
1
1
0
0
3
4
           

說句實話,這場比賽的C題感覺也就洛谷提高-難度,但是…我TM當時為什麼就想不到正解.可能打到12點腦子糊了??真是醉了,上分之路路漫漫啊

主要思路:

1. 題中需要求出sum[m]最小(sum代表字首和),那麼我們列舉一下小于m之前的所有字首和

   a [ 1 ] + a [ 2 ] + a [ 3 ] + . . . + a [ m ] > a [ 1 ] + a [ 2 ] + a [ 3 ] + . . . + a [ k ] a[1]+a[2]+a[3]+...+a[m]>a[1]+a[2]+a[3]+...+a[k] a[1]+a[2]+a[3]+...+a[m]>a[1]+a[2]+a[3]+...+a[k] 其中 k < m 其中k<m 其中k<m

   化解一下,就得出了 a [ k + 1 ] + . . . + a [ m ] < 0 a[k+1]+...+a[m]<0 a[k+1]+...+a[m]<0,也就是從m開始到2倒着的字首和要一直為負

2. 同理大于m的所有字首和我們列舉一下就會發現需要從m+1開始到n的所有字首和要一直為正.然而當時我就卡在這一步了,我當時想法是當目前的字首和大于0(以小于m為例),我們目前數字的顯然是正的,是以目前數字應該直接取負的,反之取正.但是這種貪心想法是錯誤的,因為可能目前字首和是負的,但是後來的數字加上去是正的,并且目前數字取反是最優的.舉一個當時賽時自己舉的反例:

6 5
1 5 2 8 -9 1
ans=1,直接改8即可
           

1. 然後當時腦子就轉不過來了,不知道該怎麼辦,當時的想法就是我該怎麼知道

   8

   是不是應該取負呢.現在想想為什麼當時就轉不過來呢,就差一點點了啊.好了,講講正解吧.正解就是當我們目前的字首和大于0(以小于m為例,大于m同理),我們将之前所有數字中最大的(包括自己)取出來取一個負數,這樣的話因為隻是将一個數字取反,是以我們将所有數字中最大的取負,這樣在保證我們的字首和為負的同時還保證了我們現在的字首和是最小的

接來下是具體的代碼部分:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define int long long
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int t;int m,n;int a[maxn];
signed main() {
	t=read();
	while(t--) {
		n=read();m=read();int sum=0;int ans=0;
		priority_queue<int>q1;
		for(int i=1;i<=n;i++) a[i]=read();
		for(int i=m;i>=2;i--) {
			q1.push(a[i]);sum+=a[i];
			if(sum>0) {
				int f=q1.top();q1.pop();
				sum-=2*f;
				ans++;
			}
		}
		priority_queue<int,vector<int>,greater<int> >q2;
		sum=0;
		for(int i=m+1;i<=n;i++) {
			q2.push(a[i]);sum+=a[i];
			if(sum<0) {
				int f=q2.top();q2.pop();
				sum-=2*f;
				ans++;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}