AT_abc180_d 题解
本篇题解为此题较简单做法及较少码量,并且码风优良,请放心阅读。
题目简述
现有 \(STR\) 和 \(EXP\) 两个变量,初始化分别为 \(X\) 和 \(0\),可对变量 \(STR\) 做以下两种操作:
-
将 \(STR\) 乘 \(A\),并将 \(EXP\) 自加 \(1\)。
-
将 \(STR\) 加上 \(B\),并将 \(EXP\) 自加 \(1\)。
在 \(STR < Y\) 的情况下,求 \(EXP\) 的最大值。
思路
本蒟蒻读完题目后:“贪心!”
那么贪心该怎么贪?通过题意我们很容易想到,无论是执行第一个造作还是第二个操作对 \(EXP\) 的影响不变,故就需要我们衡量操作一或二的优势。
如执行操作一比执行操作二更优,则有:
\[STR \times A < STR + B \]同时需满足:
\[STR \times A < Y \]而自信提交的我结果就可想而知了,重新看了一遍题目,发现数据范围:\(1 \le X < Y \le 10^{18}\),\(2 \le A \le 10\),\(1 \le B \le 10^9\)。
那么 \(STR \times A\) 就有爆 \(\text{long long}\) 的可能,通过简单的不等式移项可变化为:
\[STR < Y / A \]这样操作一比操作二更优的情况就解决了。又因为贪心思想,当操作二更优时可直接计算还可加多少 \(B\),直接加到 \(ans\) 里即可,因为此时再进行操作一必定超过 \(Y\) 或 \(STR \times A \ge STR + B\)。
经过以上分析,即可得到以下代码:
#include<iostream>
using namespace std;
long long x, y, a, b, ans = 0; // 开 long long
int main() {
cin >> x >> y >> a >> b; // 输入
while(x < y) {
if(x < y / a && x * a < x + b) x *= a, ans ++; // 操作一比操作二更优,防止爆 long long 优化
else break; // 操作二更优
}
ans += (y - x - 1) / b; // 计算操作二还可执行多少次
cout << ans << endl; // 输出,换行好习惯
return 0;
}
\(\text{The End!!!}\)
提交了 \(5\) 次,我崩溃了 qwq。。
标签:le,第十三,更优,小组,long,学习,STR,操作,EXP From: https://www.cnblogs.com/So-noSlack/p/17576582.html