题解：P10260 [COCI 2023/2024 #5] Rolete

· · 题解

一件有趣的事情：教练给我们期中考试，考了两场 COCI 的整套题目。。。

抛开上面不谈，这道题的质量还是不赖的。首先显然要求出询问为任意值时的答案然后查询就好。我们通过大眼观察法可以得到一个贪心：求 x 的答案，就在 x+1 的最优方案基础上操作，把高出部分一个一个拉上去（称为操作 1）和整体下降（称为操作 2）的花费做一个比较，选代价更小的那个。

这题的难点其实并非贪心，而是思考这个看起来就很假的贪心的正确性。考虑反证法。

如果你 x+1 的情况用这种方法得到了最优解，并且 x 的时候用这种方法得不到最优解，那么你一定是因为调整上面的某一步操作会让之前的代价更大但是此时的代价最小。

显然如果会这样要么是之前用 1 代价更大但是如果用 1 可以减小本次使用 2 操作的代价，但是如果你之前用 2 现在用 1 的操作代价是一样的，所以你之前用 2 是不劣的。

或者是之前用 2 代价更大但是用 2 操作可以拉下去一些本来不需要拉的窗帘，让你 1 操作的代价更小。但是你之前用 1 这下用 2 肯定也是不劣的。

综上，你照这样贪心下去肯定是不劣的，那么代码也非常简单啊。

#include<bits/stdc++.h>
#define int long long
 #define endl '\n'
using namespace std;
const int mod=998244353,inf=0x3f3f3f3f3f3f3f3f;
const int N=1e5+10,M=2e5+10;
const int m=1e5;
int n,t,s,k;
int a[N],ans[N],cnt[N];
int sl[N],sr[N];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >>n >> t >> s >> k;
    for ( int i = 1 ; i <= n ; i++ )cin >> a[i];
    for ( int i = 1 ; i <= n ; i++ )sl[a[i]]++,sr[a[i]]++;
    for ( int i = 1 ; i <= m ; i++ )sl[i]+=sl[i-1];
    for ( int i = m ; i >= 0 ; i-- )sr[i]+=sr[i+1];
    for ( int i = m-1 ; i >= 0 ; i-- )
    {
        int cost1=s+k*sl[cnt[i+1]];
        int cost2=sr[i+1+cnt[i+1]]*t;
        if(cost1<cost2)ans[i]=ans[i+1]+cost1,cnt[i]=cnt[i+1]+1;
        else ans[i]=ans[i+1]+cost2,cnt[i]=cnt[i+1];
    }
//  for ( int i = 0 ; i <= 6 ; i++ )
//      cout << ans[i] << " " << cnt[i] << endl;
    int q;cin >>q;
    while(q--){int x;cin >> x;cout << ans[x] << " ";}
    return 0;
}