题意
给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;
}
标签:Wall,Breaking,ceil,a1,int,a2,ans,1674,2.0
From: https://www.cnblogs.com/4VDP/p/16823312.html