题目描述
马上就要放暑假啦！
为了激励一下公司的员工，徐老师决定给所有人发奖金！
发奖金的方式非常简单，徐老师会在桌上一字排开 \(n\) 张纸团，每张纸团上会写着一个数字 \(a_i\)，为了平衡公司成本，这里的数字可能会存在负数
游戏规则是：每人只能抓一次，只能抓取一段连续的纸团，所有纸团上的数字和就是这次可以获得的奖金，如果有人不幸获得了负数的奖金，那么就意味着他要被扣掉对应的工资，所以徐老师也允许大家选择不抓纸团，那么奖金就是 \(0\) 元
现在石老师是第一个抽奖金的人，石老师想知道，他一共有多少种不同的方案可以获得至少 \(k\) 元的奖金？
输入格式
输入第一行包含一个整数 \(n,k\) 含义如题
输入第二行包含 \(n\) 个整数，\(a_i\) 依次表示每个纸团上的数字
输出格式
输出一个整数表示有多少种不同的方案
对于 \(100\%\) 的数据：\(1\le n \le 3\times 10^5，-10^{18}\le k \le 10^{18}，-10^9\le a_i\le 10^9\)。
点击查看
bool M1;
#include<bits/stdc++.h>
#define int long long
const int N = 2e6+10, inf = 1e18;
using namespace std;
inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return x*f;
}
int n,K,a[N],ans,mp[N]; int b[N],tot;
bool cmp(int x,int y) {return x>y;}
int get(int l,int r,int k) {int res=0;while(l<=r) {int mid=(l+r)>>1;if(b[mid]>=k) l=mid+1,res=mid;else r=mid-1;} return res;
}
void solve(int l,int r) {if(l==r) {if(a[l]>=K) ++ans;return ;}int mid=(l+r)>>1; solve(l,mid);solve(mid+1,r);tot=0;mp[mid]=a[mid];b[++tot]=mp[mid+1]=a[mid+1];for(int i=mid-1;i>=l;i--) mp[i]=mp[i+1]+a[i];for(int i=mid+2;i<=r;i++) mp[i]=mp[i-1]+a[i],b[++tot]=mp[i];sort(b+1,b+tot+1,cmp); for(int i=mid;i>=l;i--) ans+=get(1,tot,K-mp[i]);
} bool M2;
signed main() {cerr<<(&M2-&M1)/(1024*1024)<<'M'<<'B'<<endl;freopen("money.in","r",stdin);freopen("money.out","w",stdout);n=read();K=read(); if(K<=0) ans++;for(int i=1;i<=n;i++) a[i]=read();solve(1,n); return cout<<ans,0;
}
贪心+排序
- P14361 [CSP-S 2025] 社团招新 / club（官方数据）
贪心
- P5019 [NOIP 2018 提高组] 铺设道路
贪心+二分
- P4447 [AHOI2018初中组] 分组
贪心+二分
- P9755 [CSP-S 2023] 种树
贪心+二分
- P5021 [NOIP 2018 提高组] 赛道修建
二分
- P1873 [COCI 2011/2012 #5] EKO / 砍树
贪心
- P1668 [USACO04DEC] Cleaning Shifts S
二分
- P1462 通往奥格瑞玛的道路
二分
- P6099 [USACO19FEB] Dishwashing G