题目：https://codeforces.com/contest/1435/problem/E
每隔d时间造成a伤害，每次造成a伤害后c秒内，每秒都会回复b生命值，生命值回复效果的buff可以叠加。
如果无论对方多少血都是杀死对面，输出-1。否则能击杀对方的生命最大值，生命值比long long大就输出”500000500000“。
思路：
先把 1.直接杀死。2. 只有第一次能直接杀死。3 . 在回血buff叠加过程中，能造成伤害a和之后回血多少来比较。
关键是第三种情况，考虑在T时刻，回血次数t只与前面min(T,c)的时间长度内造成多少次a伤害有关。
如果写成一个大暴力就是如下
long long ans=0,tmp=ans,T=0; while(T++) { if(T<c) heal=(ll)ceil(T*1.0/d)*b;//这一刻回了多少血 else heal=(ll)ceil(c*1.0/d)*b; tmp-=heal; if(T%d==0)//取到生命最大值都是在造成a伤害后计算是最优的 { tmp+=a; if(tmp<=ans) break; else ans=tmp; } }
由于T时刻回血量heal是向上取整，以前T∈(0,d)回血b，T∈[d,2*d)回血2*b。。。。。。所以可以用一个等差数列求和直接计算。
在我们分类之后，可以发现在这种需要计算的情况只有当a>=b*c&&c>=d。
所以我们只要计算出T∈(0,c)的情况，也就是前面是一个等差数列，c秒后每秒内回血都是一个固定值ceil(c*1.0/d)*b。c秒后直接讨论a与每轮回血值就好了。
那么在c秒前，怎么找到tmp<=ans的情况呢，ts设为T=ts*d的时候达到最优，tmp<=ans就是在a<=ts*b*d的时候。
加上c秒前的限制就是ts=min(c/d,a/(b*d))+1。
#include<bits/stdc++.h> #include<ext/rope> //#include<hash_map> #define sd(x) scanf("%d",&x) #define lsd(x) scanf("%lld",&x) #define ms(x,y) memset(x,y,sizeof x) #define fu(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) #define all(a) a.begin(),a.end() using namespace std; using namespace __gnu_cxx; typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int maxn=1e5+91; const int mod=1e9+7; const int INF=1e9+7; const double pi=acos(-1); int ans[maxn],mx[maxn]; int main() {int n;sd(n); while(n--) { ll a,b,c,d; lsd(a);lsd(b);lsd(c);lsd(d); ll ans=a; if(a>b*c) printf("-1\n"); else { if(b*d>=a||c<d) printf("%lld\n",ans); else { ll ts=min(c/d,a/(b*d))+1; ans=ts*a-(ts-1)*(ts)/2*b*d; if(a<=ts*b*d) { printf("%lld\n",ans); continue; } ll heal=(ll)ceil(c*1.0/d)*b;//每次回复的生命值 //c>=d //到第一个d if(a>=(d-c%d)*heal) { printf("%lld\n",ans); } else { ans+=a-(d-c%d)*heal; if(a<=d*heal) printf("%lld\n",ans);//后面扣血和加血平衡了 else printf("500000500000\n"); } } } } return 0; }
Codeforces Round #679 (Div. 2, based on Technocup 2021 Elimination Round 1) E. Solo mid Oracle