2025年3633. 双人旋转赛车

科技前沿 • 2025-01-17 15:33 • 阅读 48

大家好，我是讯享网，很高兴认识大家。

单点时限: 2.0 sec

内存限制: 1024 MB

oxx 和 Xiejiadong 在玩一个双人旋转赛车的小游戏。

在这里插入图片描述
讯享网

他们将进行一些比赛。每局比赛必须按顺序进行，胜者会得到该局对应的分数 xi。

由于 oxx 技艺不精（每局都可以由 Xiejiadong 决定胜负），因此他给自己设置了初始分数 k，希望自己能够一直领先 Xiejiadong。

不过 Xiejiadong 识破了 oxx 的诡计，现在 Xiejiadong 想知道自己至少需要赢几局才可以使得自己能够在某一时刻的比分不落后于 oxx。

若无法达到则输出 −1。

第二行 n 个整数 xi (1≤xi≤109)，表示每局游戏的分数。

样例
input
3 3
4 1 2
output
1
input
3 7
1 2 3
output
-1
提示
样例一：Xiejiadong 只需要赢第一局，即可获得 4 分，这时候就不落后于 oxx 3 分。

样例二：Xiejiadong 全胜也领先不了。
在这里插入图片描述

/* 思路：贪心 每次把最小的还给oxx 使用优先队列表示在队列中的是xiejiadong要选的 */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int maxn=1e6+10; priority_queue<ll,vector<ll>,greater<ll> >q; ll sum1,sum2,a[maxn]; int n,now,ans; int main() { 
    scanf("%d%lld",&n,&sum1); for(int i=1; i<=n; ++i) scanf("%lld",&a[i]); ans=n+1; for(int i=1; i<=n; ++i) { 
    sum2+=a[i];//当前选了之后得分  q.push(a[i]); now++;//now=q.size() while(sum2-q.top()>=sum1+q.top()) { 
   //去掉一局得分仍可以满足就去掉最小的 sum2-=q.top();//不要此局分数  sum1+=q.top(); q.pop(); now--;//胜局数减一 } if(sum2>=sum1)ans=min(ans,now); } printf("%d\n",ans==n+1?-1:ans); return 0; }

讯享网

2025年3633. 双人旋转赛车

相关推荐