2 solutions
-
0
思路
这道题因为其他原因导致数据很水,暴力都能过。我这里提供最开始的想法。用二分去写。 二分答案,对每一个时间t,确定到t可以观察到多少个星星闪耀。 然后这里有三种情况 三种情况:
1:第i个星星开始时间大于t,直接跳过。
2:开始时间在l和t之间,
3:开始时间t小于l
ac code
#include<bits/stdc++.h> typedef long long LL; using namespace std; const int N = 1e5 + 10; int n; LL a[N],b[N],l,r,tgt; bool check(LL x) { LL cnt = 0; for(int i = 1;i <= n;++ i) { if(a[i] > x)continue;//还没开始闪 if(a[i] <= x && a[i] >= l)//我当时都忘了还要大于l { cnt += (x - a[i])/b[i] + 1; if(cnt >= tgt)return true; } else { cnt += (x - a[i])/b[i] - (l - 1 - a[i])/b[i]; if(cnt >= tgt)return true; } } return false; } int main () { cin >> n; for(int i = 1;i <= n;++ i) { cin >> a[i];//开始时间 } for(int i = 1;i <= n;++ i) { cin >> b[i];//周期 } cin >> l >> r >> tgt; LL l1 = l; LL r1 = r; while(l1 < r1)//二分左 { LL m = (l1 + r1) >> 1; if(check(m))r1 = m; else l1 = m + 1; } check(l1) ? cout << l1 : cout << "-1"; return 0; }
-
0
#include<cstdio> typedef long long ll;//不开long long 见祖宗。。。 ll l,r,c,start ; ll n ,a[100005],b[100009]; bool check(ll x)//一定要注意!!!不要转换类型错了!!! { ll sum = 0; for(int i = 1;i <= n;i++) { if(b[i] > x)continue; else if(b[i] < start) { sum += (x - b[i])/a[i] - (start - 1 - b[i])/a[i];//start应该包含在里面,减去start-1以及前的区间 } else sum += (x-b[i])/a[i] + 1; //加一是当时开始亮的时候也要算一次 if(sum >= c)return true; } return false; } int main() { scanf("%lld",&n); for(int i = 1;i <= n;i++) { scanf("%lld",&b[i]); } for(int i = 1;i <= n;i++) { scanf("%lld",&a[i]); } scanf("%lld%lld%lld",&l,&r,&c); start = l; ll mid = 0;//救命,开的int一不小心就超时,改了我好久,可恶。。。。 while(l < r)//这里是一个从小到大的隐藏条件 {//举个例子:其中check(l+3)表示从l——l+3,这个区间里面的计数 //并且,因为是闪一下记一次,check(l+4)肯定是不小于check(l+3)的 //所以这一定是个递增的序列,我们就可以用二分啦!!! mid = l+ r>>1; if(check(mid))r = mid; else l = mid+1; } if(check(l))printf("%lld",l);//判断一下这个数是否 >=c else puts("-1"); return 0; }
- 1
Information
- ID
- 7004
- Time
- 500ms
- Memory
- 256MiB
- Difficulty
- 8
- Tags
- # Submissions
- 163
- Accepted
- 21
- Uploaded By