思路:
先来看组样例
1 5 12 23......
显然对于数2,3,4来说,取他们本身是最优的。
再继续往后看
6:2次
7:3次
8:4次
9:5次
10:2次
11:3次
再继续...
13:2次
14:3次
15:4次
16:5次
17:2次
18:3次
19:4次
20:5次
21:6次
22:3次
...
继续枚举
我们可以发现,在区间[ai, ai+1]中,都有个“峰值”,代表着当数b属于区间[ai, ai+1],取峰值为最优解。
比如区间[a1, a2]的峰值为4,区间[a2, a3]峰值为9,区间[a3, a4]的峰值为21...
观察可以发现,第i个峰值,为ka[i] + "第i - 1个峰值"(这个数整体要小于a[i + 1])
注意,如果ka[i] + "第i - 1个峰值"恰好等于a[i + 1],则要将整体减去一个a[i](从贪心上讲这样最优)
那么怎么求出每个峰值的答案呢,由峰值的递推可知,第i个峰值的答案为k + 第i - 1个峰值的答案。
令m为峰值数组,ans为峰值的答案数组,用tmp数组存每次递推式的k,则有如下代码:
m[1] = a[2] - 1; for (int i = 2; i <= n - 1; i++) { tmp[i] = (a[i + 1] - m[i - 1]) / a[i]; m[i] = tmp[i] * a[i] + m[i - 1]; if (m[i] == a[i + 1]) { m[i] -= a[i]; tmp[i] -= 1; } } ans[1] = a[2] - 1; for (int i = 2; i <= n - 1; i++) { ans[i] = tmp[i] + ans[i - 1]; }
下面开始求解,对于每次输入的询问b,我们可以二分求出最大的pos,使得m[pos]≤b
注意,如果b满足b属于[mpos, apos + 1],则由于m数组的定义,答案应该取m[pos],否则,如果b > apos + 1, 答案应该为k*a[pos + 1] + "第pos个峰值"(类似于峰值数组的递推,其中这个数整体要小于b)
有如下代码:
pos = lower_bound(m + 1, m + n, b) - m; if (m[pos] != b) pos--; if (b <= a[pos + 1]) { cout << m[pos] << " " << ans[pos] << "\n"; } else { ans1 = a[pos + 1] * ((b - m[pos]) / a[pos + 1]) + m[pos]; ans2 = ((b - m[pos]) / a[pos + 1]) + ans[pos]; cout << ans1 << " " << ans2 << "\n"; }
注意特判b <= a[2] - 1的情况
AC代码如下:
#include <bits/stdc++.h> using namespace std; #define ll long long ll a[200010]; ll m[200010]; ll ans[200010]; ll tmp[200010]; ll n; ll q; ll b; ll ans1; ll ans2; ll pos; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } m[1] = a[2] - 1; for (int i = 2; i <= n - 1; i++) { tmp[i] = (a[i + 1] - m[i - 1]) / a[i]; m[i] = tmp[i] * a[i] + m[i - 1]; if (m[i] == a[i + 1]) { m[i] -= a[i]; //如果峰值数组恰好为a[i + 1],则减去一个a[i] tmp[i] -= 1; //倍数-1 } } ans[1] = a[2] - 1; for (int i = 2; i <= n - 1; i++) { ans[i] = tmp[i] + ans[i - 1]; } cin >> q; for (int i = 1; i <= q; i++) { cin >> b; if (b < a[2]) { cout << b << " " << b << "\n"; } else { pos = lower_bound(m + 1, m + n, b) - m; if (m[pos] != b) pos--; if (b <= a[pos + 1]) { cout << m[pos] << " " << ans[pos] << "\n"; } else { ans1 = a[pos + 1] * ((b - m[pos]) / a[pos + 1]) + m[pos]; ans2 = ((b - m[pos]) / a[pos + 1]) + ans[pos]; cout << ans1 << " " << ans2 << "\n"; } } } return 0; }