題意
給n個數的數列a[n]，可以進行任意次操作，每次選取一個位置i，a[i]-=2，a[i-1]-=1,a[i+1]-=1，問最少幾次操作可以讓任意兩個值<=0
提示
需要進行分類討論，分成三種情況討論
1. 兩個數是相鄰的，那么則需要解方程，x，y代表兩點分別進行多少次
2. 兩個數間隔一位的話，那么需要解方程，x，y代表兩點分別進行多少次，z代表中間點需要多少次
3. 任意兩點，直接排序取兩個最小值ceil（x/2）即可
這道題比較簡單，看完題目以后解題思路就比較明顯了，比賽的提交很多人被hack了，估計是一些邊界值考慮出錯導致的，代碼實作也比較簡單
代碼
#include<bits/stdc++.h>
using namespace std;
int a[200005];
int calc1(int a1, int a2) {
if (a1 < a2)swap(a1, a2);
if (a1 >= 2 * a2) {
return ceil(a1 / 2.0);
}
return ceil((a1 + a2) / 3.0);
}
int calc2(int a1, int a2) {
return min(1 + ceil((a1 - 1) / 2.0) + ceil((a2 - 1) / 2.0), ceil((a1) / 2.0) + ceil((a2) / 2.0));
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int ans = INT_MAX;
for (int i = 1; i < n; i++) {
ans = min(ans, calc1(a[i], a[i + 1]));
}
for (int i = 1; i < n - 1; i++) {
ans = min(ans, calc2(a[i], a[i + 2]));
}
sort(a + 1, a + 1 + n);
ans = min(ans, int(ceil(a[1] / 2.0) + ceil(a[2] / 2.0)));
cout << ans << endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/519159.html
標籤：其他
上一篇：W5500使用備忘