題目鏈接
題目大意
有一個長度為 n 的數組
做操作使這個數組不遞減:
- 把一個數分成兩個數,例如:x 分為 a 和 b, x == a + b
求最小操作次數
思路
見注釋
代碼
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N];signed main()
{int T;cin >> T;while (T -- ){int n; cin >> n;for (int i = 1; i <= n; i ++ ) cin >> a[i];int ans = 0;for (int i = n - 1; i >= 1; i -- ) {if (a[i] > a[i + 1]){int x = a[i] / a[i + 1]; //分成幾個數 if (a[i] % a[i + 1] != 0) x ++; //如果有余數,那就多分出了一個數a[i] = a[i] / x; //使分成的那幾個數的最小值盡可能大,就取一下平均值// 例如//a[i] = 13, a[i + 1] = 3//直接除后的方法使我們知道需要分成5個數字://1, 3, 3, 3, 3//但是1太小了,會影響a[i - 1] //要使它變大,就讓13 / 5, 取平均值//得到 2, 2, 2, 2, 2, 余3,多的3就放在最后三位//即 2, 2, 3, 3, 3,//因為相當于是把多的往少的勻,所以絕對不會影響到a[i + 1] ,即最大值不會超過a[i + 1] ans += (x - 1);// x是分成的數的個數,x - 1就是需要的步驟數}}cout << ans << endl; }return 0;
}
總結
復述一遍思路:
當前面的數比后面的數大時,就需要拆分這個數,拆成盡可能少的個數,每個數還要盡可能大,這些數取決于后一個數,當前數 除以后一個數,如果能整除,那就分為那么多個數,且是最大的,若不能,則會多分出一個數,要使它們盡可能大(最小值最大),就是要讓那個余數最大,但余數肯定大不過除數,就把這個數平均分為這么多個數,多出來的就平均分配進分出來的每一個數里面,實現最大化最小值的操作。