网站设计合同范本,网站seo系统,有内涵的公司名,如何做企业介绍题目链接
B. Milena and Admirer
题意
给一个长度为 n n n的序列#xff0c;我们通过操作使这个序列变成非递减序列 操作#xff1a;对 a [ i ] a[i] a[i]#xff0c;我们将 a [ i ] a[i] a[i]删除#xff0c;将 a [ i ] − x 、 x a[i]-x、x a[i]−x、x插入原位置…题目链接
B. Milena and Admirer
题意
给一个长度为 n n n的序列我们通过操作使这个序列变成非递减序列 操作对 a [ i ] a[i] a[i]我们将 a [ i ] a[i] a[i]删除将 a [ i ] − x 、 x a[i]-x、x a[i]−x、x插入原位置要求 x a [ i ] xa[i] xa[i] 求最小的操作次数
题解
考虑贪心 对于满足 a [ i ] a [ i 1 ] a[i]a[i1] a[i]a[i1]的 i i i我们不去操作 对于不满足条件的 i i i我们考虑将 a [ i ] a[i] a[i]拆成k个满足条件并且尽可能大的数。这里k最多为 a [ i ] − 1 a[i]-1 a[i]−1因为一个数最多全部拆成1。 考虑如何拆才能使答案最优我们希望当前拆完的数尽可能大在满足拆完的所有数都小于 a [ i 1 ] a[i1] a[i1]的情况下。因为我们当前拆完的数的最小值会影响前面的数的拆分我们肯定是希望拆完之后最小值最大的如何才能达到最小值最大呢 考虑去平均拆。 对于 a [ i 1 ] a [ i ] a[i1]a[i] a[i1]a[i]需要将拆 c n t a [ i ] / a [ i 1 ] ( a [ i ] cnta[i]/a[i1](a[i]%a[i1]!0) cnta[i]/a[i1](a[i]成这么多个数需要拆 c n t − 1 cnt-1 cnt−1次还需要去维护一个最小值 a [ i ] / c n t a[i]/cnt a[i]/cnt从后往前扫一遍维护最小值统计答案即可。
代码
#include bits/stdc.h
#define int long long
#define rep(i,a,b) for(int i (a); i (b); i)
#define fep(i,a,b) for(int i (a); i (b); --i)
#define pii pairint, int
#define ll long long
#define db double
#define endl \n
#define x first
#define y second
#define pb push_backusing namespace std;void solve() {int n;cinn;vectorinta(n1);rep(i,1,n) {cina[i];}int cur1e9;int ans0;//倒着枚举一遍fep(i,n,1) {if(a[i]cur){cura[i];}else if(a[i]%cur0){ansa[i]/cur-1;}else{int cnta[i]/cur1;ans(cnt-1);cura[i]/cnt;}}coutansendl;
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// freopen(1.in, r, stdin);int _;cin_;while(_--)solve();return 0;
}总结
这道题目主要是要想清楚对于一个数如何拆分才能对后面的影响最小。
