题解：P13009 【MX-X13-T4】「KDOI-12」好胜是人的本能，功利是社会的本性。

CQ_Bab · 2025-07-01 17:17:11 · 题解

思路

首先我们可以发现对于一个数 x 在进行最多 2 次操作之后一定会出现重复，也就是第 1 次操作的值一定等于第 3 次操作之后的值，考虑证明，我们假设此数为 x 那么在进行完第一次操作之后设 y=\lfloor m\div x\rfloor 然后我们考虑整数分块，我们假设 m\div k=y 时的 k 的取值范围为 l\sim r 然后我们的发现 l\leq x\leq r，然后对于第二次操作的值一定是 r 所以对于第三次的值就又是 y 了，所以证毕。

然后我们就可以把每个 i 上能取的值 j 给算出来，然后考虑 dp，我们设 f_{i,j} 表示第 i 个选 j 把 1\sim i 消完的最小代价，那么我们的转移就是 f_{i,j}=\min(f_{i-1,k}+\max(0,j-k))，答案也很简单就是 \min(f_{n,1},f_{n,0},f_{n,2})。

代码

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define int long long
#define fire signed
#define il inline
template<class T> il void print(T x) {
    if(x<0) printf("-"),x=-x;
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
template<class T> il void in(T &x) {
    x = 0; char ch = getchar();
    int f = 1;
    while (ch < '0' || ch > '9') {if(ch=='-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    x *= f;
}
int T=1;
int n,m;
const int N=1e5+10;
int a[N];
int f[N][3],vis[N][3];
void solve() {
    in(n),in(m);
    int s=0,res=0;
    rep(i,1,n) rep(j,0,2) vis[i][j]=false;
    rep(i,1,n) {
        in(a[i]);
        int x0=a[i],x1=m/x0,x2=m/x1;
        int dis=max({x0,x1,x2});
        s+=dis;
        if(dis==x0) vis[i][0]=1;
        if(dis==x1) vis[i][1]=1;
        if(dis==x2) vis[i][2]=1;
    }
    int cnt=0;
    rep(i,0,n) rep(j,0,2) f[i][j]=1e18;
    f[0][0]=0;
    rep(i,1,n) {
        rep(k,0,2) if(vis[i][k]) rep(j,0,2) f[i][k]=min(f[i][k],f[i-1][j]+max((int)0,k-j));
    }
    printf("%lld %lld\n",s,min({f[n][0],f[n][1],f[n][2]}));
}
fire main() {
    in(T);
    while(T--) {
        solve();
    }
    return false;
}