重发一下,蒟蒻贪心80分求助
查看原帖
重发一下,蒟蒻贪心80分求助
1019983
Czero_2023楼主2023/8/18 11:11

在大神的指导下发现要开longlong,但是TLE

用的贪心,修修改改,不超时了,但是WA了#8#9

本蒟蒻卡了有半个月了,求助!

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n,maxnum=200005,a[200005],b,ans;
    //maxnum为答案的上限
    long long m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        cin>>b;maxnum=min(maxnum,b+a[i]);
        //最小即上限
    }
    sort(a+1,a+n+1);
    ans=a[1];//答案至少有a[1]
    for(int i=1;i<=n;i++)
    {
        //从最小的开始依次补牌
        int t=a[i+1]-a[i];//要补的牌数
        if(m>=i*t&&ans+t<maxnum&&a[i]<a[i+1])
        //剩余空卡牌大于需要卡牌,答案不超额,且需要画牌
        {
            //数组从1开始,加一遍就是i张牌
            ans+=t;m-=i*t;//一次多加,减少循环
        }
    }
    cout<<ans;
    return 0;
}
2023/8/18 11:11
加载中...