阅读量:1
天上有 n 颗星星，每颗星星自第 bi 秒开始（包含第 bi 秒），每 ai 秒便会闪烁一次，小度 今晚有一点失眠，所以他想来数星星，天上的星星每闪烁一次，小度便会在心中记一次数，如果同时有 x 颗星星在闪烁，小度也会计数 x 次。
假设小度今晚会从第 l 秒开始数，第 r 秒天便亮了，但是在计数到 c 次及以上的时候，小度便会睡着。
请问你能帮小度预估，今晚是否能睡着吗？如果能，将会在多少秒时睡着。
格式
输入格式：
第 1 行读入 1 个整数 n，代表天上的星星个数；
第 2 行读入 n 个整数 ai， 代表第 𝑖i 个星星的闪烁周期；
第 3 行读入 n 个整数 bi， 代表第 𝑖i 个星星的开始闪烁时间；
第 4 行读入 3 个整数 l,r,c，代表开始计数时间，结束时间，计数睡着的次数。
数据保证 1≤n≤10^5，1≤ai,bi,l,r,c≤10^18，l≤r。
输出格式：
如果小度能够睡着，那么输出小度睡着的时候，否则输出 -1。
样例 1
输入：
2 1 2 1 1 1 10 4
输出：
3
样例 2
输入：
1 1 1 30 40 12
复制
输出：
-1
复制
样例 3
输入：
3 1 3 5 3 5 9 1 30 20
输出：
16
样例 4
输入：
1 2 3 1 1000000000000000000 499999999999999999
输出：
999999999999999999
复制
备注
样例1解释：
第 1 秒，星星 1 与 星星 2 闪烁一次；
第 2 秒，星星 1 闪烁一次；
第 3 秒，星星 1 与 星星 2 闪烁一次；
在第 3 秒时，所有星星共 5 次，大于等于 4 次，所以小度会在第 3 秒睡着。
所以答案为 3。
样例2解释：
第 30 秒至第 40 秒期间，星星共闪烁 11 次，没有满足小度会睡着的条件，输出 -1。
思路：二分求解，对每一个时间t，确定到t可以观察到多少个星星闪耀。（题目不难，就是可能有细节错，建议先打个草稿分一下情况）（ps:这星耀难度像签到，hh）
三种情况：
1：第i个星星开始时间大于t，直接跳过。
2：开始时间在l和t之间，计算t到b[i]的闪耀次数。
3：开始时间t小于l，计算l-1到b[i]和t到b[i]的闪耀次数，然后相减。（博主一开始一直是l到b[i]，一直错，/(ㄒoㄒ)/~~）
代码;
#include<bits/stdc++.h> using namespace std; #define int long long const int N=1e5+10; int a[N]; int b[N]; int l,r,c,n; int l1,r1; int check(int x){ int count=0; for(int i=1;i<=n;i++) if(b[i]>x)continue; else if(b[i]<=x&&b[i]>=l){ count=count+(x-b[i])/a[i]+1; if(count>=c)return 1; } else { count=count+(x-b[i])/a[i]-(l-1-b[i])/a[i]; if(count>=c)return 1; } return 0; } signed main(){ scanf("%lld",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<=n;i++) scanf("%lld",&b[i]); scanf("%lld%lld%lld",&l,&r,&c); l1=l; r1=r; while(l1<r1){ int mid=(l1+r1)/2; if(check(mid))r1=mid; else l1=mid+1; } if(check(r1))printf("%lld",r1);else printf("-1"); return 0; }喜欢博主的话，点个关注哦😙
