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

Lovely_Rabbit · 2025-06-29 17:10:50 · 题解

多测不清真糖吧。

首先这个向下取整手玩一下发现除超过 2 次就一定进循环。

那么就只需要考虑三种情况的取值，取最大第一问就解决了。

接下来第二问。

做过积木大赛的同学看了以后觉得很熟悉，于是贪心上去挂爆了。

事实上修改次数不会影响大小时多修改几次可能会有利于操作减少，所以贪心炸了。

考虑 dp，设 dp_{i,j} 表示第 i 个数取 j 时最小的操作次数。

转移从上一个的三种情况模拟下来取最小就行。

注意判合法与多测清空。

那么做完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005];
int dp[100005][4];
int ans,ret;
void solve(){
    ans=ret=0;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        a[i]=0;
        int x;
        cin>>x;
        int A=x;
        int B=m/A;
        int C=m/B;
        // cout<<A<<' '<<B<<' '<<C<<' ';
        ans+=max({A,B,C});
        if(A>=B&&A>=C)a[i]+=1;
        if(B>=A&&B>=C)a[i]+=2;
        if(C>=A&&C>=B)a[i]+=4;
        // cout<<' '<<a[i]<<'\n';
    }
    dp[0][1]=dp[0][2]=1e9;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=2;j++){
            if(a[i]&(1<<j))dp[i][j]=min({dp[i-1][0]+max(0ll,j-0),dp[i-1][1]+max(0ll,j-1),dp[i-1][2]+max(0ll,j-2)});
            else dp[i][j]=1e9;
            // cout<<dp[i][j]<<' ';
        }//cout<<'\n';
    }
    cout<<ans<<' ';
    cout<<min({dp[n][0],dp[n][1],dp[n][2]})<<'\n';
}
signed main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}