题解 CF1354A 【Alarm Clock】
囧仙
2020-05-18 19:03:16
## 题目大意
小$P$每天要睡足$a$分钟。他定了一个闹钟,会在$b$分钟后响起。如果此时小$P$还没有睡足$a$分钟,那么他会定一个$c$分钟的闹钟,并花费$d$分钟入睡。如果他被吵醒后仍未达到$a$分钟,那么他会再定$c$分钟闹钟并花费$d$分钟入睡……如果某次闹钟想起时他已经睡足了$a$分钟,他就会起床。请问他一共要花费多少分钟才会起床,或者他永远不会起床。
$T$组数据。$1\le a,b,c,d\le 10^9$。
## 题解
很显然,小$P$第一次醒来会是在$b$分钟之后。我们检查他是否睡足了$a$分钟,接下来就可以进入一个循环了。
每个循环长度为$c$分钟。在这$c$分钟内他会有$c-d$分钟睡觉。因而,他一共需要经历的时间为:
$$b+c\times \left\lfloor\frac{a-b}{c-d}\right\rfloor$$
要注意的是,如果$d\ge c$,那么每个循环他都无法睡着,也就是永远无法睡足$a$分钟。
## 参考代码
```cpp
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l;i<=r;i++)
#define dn(l,r,i) for(int i=l;i>=r;i--)
using namespace std;
typedef long long LL;
const int INF =2147483647;
LL qread(){
LL w=1,c,ret;
while((c=getchar())> '9'||c< '0')
w=(c=='-'?-1:1); ret=c-'0';
while((c=getchar())>='0'&&c<='9')
ret=ret*10+c-'0';
return ret*w;
}
LL a,b,c,d;
int main(){
dn(qread(),1,T){
a=qread(),b=qread(),c=qread(),d=qread();
if(a<=b) printf("%lld\n",b); else
if(c<=d) puts("-1"); else{
printf("%lld\n",b+((a-b-1)/(c-d)+1)*c);
}
}
return 0;
}
/*
1
1000000000 1 999999999 0
*/
```