70pt,但是吧WA的样例下载下来发现输出和答案一样
查看原帖
70pt,但是吧WA的样例下载下来发现输出和答案一样
456675
a_sad_soul楼主2023/9/15 21:41

下面是代码:

#include<bits/stdc++.h>
#define MAXN 5000005
using namespace std;
long long F[MAXN],S[MAXN];
struct node{
    int id;
    long long num;
}id[MAXN];
bool cmp(node a,node b){return a.num<b.num;}
long long n,m;
long long maxx(int i)
{
    long  long sum=F[id[i].id];
    int j=id[i].id-1;
    while(j>=1)
        if(id[i].num>=S[j])
            sum+=F[j--];
        else break;
    j=id[i].id+1;
    while(j<=n)
        if(id[i].num>=S[j])
            sum+=F[j++];
        else break;
    return sum;
}

int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld%lld",&F[i],&S[i]);
        id[i].id=i,id[i].num=S[i];
    }
    sort(id+1,id+1+n,cmp);
    int l=1,r=n,mid,ans;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(maxx(mid)>=m)
            ans=mid,r=mid-1;
        else 
            l=mid+1;
    }
    cout<<id[ans].num<<endl;
    return 0;
}
2023/9/15 21:41
加载中...