G. Gears （2022 ICPC Southeastern Europe Regional Contest. ）

G. Gears

思路：
本身这个题并不难，奈何卡了很久后看了题解才做出来，感觉自己好笨。

很容易想到的是，只要确定了一个齿轮的位置，其他齿轮的位置都可以直接推出来。所以当前目标是如何确定第一个齿轮的位置。
令$x[i]$为第$i$个轴的坐标，$s[i]$为第$i$个轴上齿轮的半径，则有递推式：
$s[i]=x[i]-x[i-1]-s[i-1]$
又最左侧轴对应齿轮的半径为 $s[1]$ ，容易得知$s[i]$的形式为:
$s[i]=a_i+s[1]$ , $i$ 为奇数
$s[i]=a_i-s[1]$ , $i$ 为偶数
所以令$s[1]=0$ 即可递推求得$a[i]$, 再分奇偶找到$a_i$的最大值$a_{max奇}$和$a_{max偶}$，此时$s_i$也应该最大，所以半径最大的齿轮($r_{max}$)一定在这两个位置之一。
为了方便检验，可以得到$s[1]$ = $r_{max}-a_{max奇}$ 或 $a_{max偶}-r_{max}$
最后分别验证一下这两个结果，找到成立的情况输出结果即可。

代码:

#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;
}

原文地址：https://blog.csdn.net/2303_79310336/article/details/142714936

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！