此题由于二分板子没记清楚，导致循环出错。

后来看了题解才知道c++里有专门二分求>=k的位置的函数

在从小到大的排序数组中：
lower_bound( begin,end,num)。该函数返回的是第一个大于等于num的第一个数字地址，减去一个数组起始地址即可得到数字在数组中的下标。

upper_bound( begin,end,num)则是大于num的第一个数字。

在从大到小的排序数组中：
lower_bound( begin,end,num,greater<type>() )，

upper_bound( begin,end,num,greater<type>() )

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+10;
  int a[N],b[N],c[N];
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=0,j=0;i<n;i++)
    {
      scanf("%d",&a[i]);
      if(i!=0){
       b[j++]=a[i]-a[i-1];
    }
    }
    sort(b,b+n-1);
    for(int i=0,j=0;i<=n-1;i++)
        c[++j]=b[i]+c[i];
    while(q--)
    {
        int k,p;
        scanf("%d%d",&k,&p);
        int pos=lower_bound(b, b+n-1, k)-b;
        long long sum=c[n-1]-c[pos]-(n-pos-1)*k;
        if(sum>=p)printf("Yes\n");
        else printf("No\n");
    }
}

兔崽小孩

全站热榜

创作者周榜