B3799题解

Light_az · 2023-06-22 18:27:20 · 题解

题意

有两种操作：

• 将 n 个数全部添加 k。

• 求 n 个数的非负数和。

分析

这道题目显然二分才是最优解。

我们考虑使用变量 cnt 记录增加值总和，然后先进行排序，保证数据递减，然后二分从 n 个数中找到最小的 a_i 使 a_i + cnt 为非负数。

此时包括 a_i 及其前面的值都是非负数，然后累加求出答案。

但是考虑数据范围我们添加前缀和优化，先预处理求出 n 个数的前缀和，然后由于有添加操作，所以我们将答案加上：非负数个数 \times cnt 即可。

代码

#include<bits/stdc++.h>
#define ll long long
#define F(i,j,n) for(ll i=j;i<=n;i++)
#define D double
#define Test ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
const int N=1e6+10;
ll n,m,k,x,y,u,v,w,cnt,ans,t,l,r,len,T,id;
ll mn=INT_MAX,mx=0,p,opt;
ll a[N],sum[N];
bool cmp(ll a,ll b){
    return a>b;
}
ll get(){//二分
    ll ans=-1,l=1,r=n;
    while(l<=r){
        ll mid=(l+r)/2;
        if(a[mid]+cnt>0) ans=mid,l=mid+1;//最小的非负数
        else r=mid-1;
    }
    return ans;
}
int main(){
    Test;
    cin>>n>>m;
    F(i,1,n) cin>>a[i]; 
    sort(a+1,a+1+n,cmp);//排序保证二分
    F(i,1,n) sum[i]=sum[i-1]+a[i];//前缀和
    F(i,1,m){
        cin>>opt;
        if(opt==1) cin>>k,cnt+=k;//累加
        else{
            id=get();
            if(id==-1) cout<<"0\n";//如果没有非负数，不选择
            else cout<<sum[id]+id*cnt<<"\n";//前缀和加上累计添加的值 * 非负数个数
        }
    }
    return 0;
}