G. Gears
思路:
本身这个题并不难,奈何卡了很久后看了题解才做出来,感觉自己好笨。
很容易想到的是,只要确定了一个齿轮的位置,其他齿轮的位置都可以直接推出来。所以当前目标是如何确定第一个齿轮的位置。
令 x [ i ] x[i] x[i]为第 i i i个轴的坐标, s [ i ] s[i] s[i]为第 i i i个轴上齿轮的半径,则有递推式:
s [ i ] = x [ i ] − x [ i − 1 ] − s [ i − 1 ] s[i]=x[i]-x[i-1]-s[i-1] s[i]=x[i]−x[i−1]−s[i−1]
又最左侧轴对应齿轮的半径为 s [ 1 ] s[1] s[1] ,容易得知 s [ i ] s[i] s[i]的形式为:
s [ i ] = a i + s [ 1 ] s[i] = a_i + s[1] s[i]=ai+s[1] , i i i 为奇数
s [ i ] = a i − s [ 1 ] s[i] = a_i - s[1] s[i]=ai−s[1] , i i i 为偶数
所以令 s [ 1 ] = 0 s[1]=0 s[1]=0 即可递推求得 a [ i ] a[i] a[i], 再分奇偶找到 a i a_i ai的最大值 a m a x 奇 a_{max奇} amax奇和 a m a x 偶 a_{max偶} amax偶,此时 s i s_i si也应该最大,所以半径最大的齿轮( r m a x r_{max} rmax)一定在这两个位置之一。
为了方便检验,可以得到 s [ 1 ] s[1] s[1] = r m a x − a m a x 奇 r_{max} - a_{max奇} rmax−amax奇 或 a m a x 偶 − r m a x a_{max偶}-r_{max} amax偶−rmax
最后分别验证一下这两个结果,找到成立的情况输出结果即可。
代码:
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int,int>
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
using namespace std;
const int N = 500005;
int n;
int s[N];
int r[N];
int a[N];
int t[N];
int ans[N];bool check(int x) { //检验最左侧齿轮半径为x的情况t[1] = x;for (int i = 2; i <= n; i++) {t[i] = s[i] - s[i - 1] - t[i - 1];}for (int i = 1; i <= n; i++) {ans[i] = t[i];}sort(t + 1, t + n + 1);for (int i = 1; i <= n; i++) {if (t[i] != r[i]) {return false;}}return true;
}void solve() {cin >> n;for (int i = 1; i <= n; i++) {cin >> s[i];}for (int i = 1; i <= n; i++) {cin >> r[i];}sort(r + 1, r + n + 1);int mj, mo = -INF;mj = a[1] = 0;mo = a[2] = s[2] - s[1];for (int i = 3; i <= n; i += 2) {a[i] = s[i] + s[i - 2] - 2 * s[i - 1] + a[i - 2];mj = max(mj, a[i]);}for (int i = 4; i <= n; i += 2) {a[i] = s[i] + s[i - 2] - 2 * s[i - 1] + a[i - 2];mo = max(mo, a[i]);}if (check(r[n] - mj)) {for (int i = 1; i <= n; i++) {cout << ans[i] << " ";}} else if (check(mo - r[n])) {for (int i = 1; i <= n; i++) {cout << ans[i] << " ";}}
}signed main() {cin.tie(0)->ios::sync_with_stdio(0);int T = 1;
// cin >> T;while (T--) {solve();}return 0;
}