单页网站有哪些,重庆建设机电网站,万户网络销售,杭州市建设工程招标平台天上有 n 颗星星#xff0c;每颗星星自第 bi 秒开始#xff08;包含第 bi 秒#xff09;#xff0c;每 ai 秒便会闪烁一次#xff0c;小度 今晚有一点失眠#xff0c;所以他想来数星星#xff0c;天上的星星每闪烁一次#xff0c;小度便会在心中记一次数#xf…天上有 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^51≤ai,bi,l,r,c≤10^18l≤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ㄒ)/~~
代码;
#includebits/stdc.h
using namespace std;
#define int long long
const int N1e510;
int a[N];
int b[N];
int l,r,c,n;
int l1,r1;
int check(int x){int count0;for(int i1;in;i)if(b[i]x)continue;else if(b[i]xb[i]l){countcount(x-b[i])/a[i]1;if(countc)return 1;}else {countcount(x-b[i])/a[i]-(l-1-b[i])/a[i];if(countc)return 1;}return 0;
}
signed main(){scanf(%lld,n);for(int i1;in;i)scanf(%lld,a[i]);for(int i1;in;i)scanf(%lld,b[i]);scanf(%lld%lld%lld,l,r,c);l1l;r1r;while(l1r1){int mid(l1r1)/2;if(check(mid))r1mid;else l1mid1;}if(check(r1))printf(%lld,r1);else printf(-1);return 0;
}
喜欢博主的话点个关注哦
