兔崽小孩＜每日一题＞

题目：

题目链接：登录—专业IT笔试面试备考平台_牛客网牛客网是互联网求职神器，C++、Java、前端、产品、运营技能学习/备考/求职题库，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://ac.nowcoder.com/acm/contest/23480/I

思路详细：

求出每次发空间的时间间隔

对其从大到小进行排序

并对每段时间间隔的数字第一次出现的位置进行标记

然后进行前缀和

这样我们每次求睡眠时间就只需要

找到时间间隔里面刚好大于 k (入睡时间)

的数的位置

然后直接输出该位置上的数就行了（因为从大到小以及进行了前缀和）

代码详解：

#include<stdio.h>
#include<iostream>
using namespace std;
#include<cmath>
#include<algorithm>
typedef long long ll;
ll t[(ll)1e6+6] = { 0 };//存储每两次间隔的时间
ll id[(ll)1e8+6] ={ 0 };//
int main()
{ll n, q, k, p, ever = 0, now = 0;ll maxx = 0;scanf("%lld%lld", &n, &q);for (ll i = 0; i < n; i++){scanf("%lld", &now);t[i]= now - ever;//存储间隔maxx = max(maxx, now - ever);//间隔时间的最大值ever = now;}t[0] = 0;//去掉一开始sort(t+1, t + n+1, greater<int>());//从大到小排序for (ll i = 1; i < n; i++){if (id[t[i]] == 0) id[t[i]] = i;//记录下间隔时间第一次出现的位置t[i] += t[i - 1];//前缀和，方便直接睡眠时间的结果}while (q--){scanf("%lld%lld", &k, &p);ll tmb = k;while (id[tmb] == 0) tmb++;//找到最近大于k最近的时间间隔的位置if (k > maxx){printf("No\n");continue;}//没有能够在时间段入睡的情况else{if (t[id[tmb]]-id[tmb]*k>=p)//通过前缀和判断是否满足睡眠时间printf("Yes\n");elseprintf("No\n");}}return 0;
}

PS:今人不见古时月，今月曾经照古人。____李白《把酒问月·故人贾淳令予问之》