P11309 纷飞的樱花雨 题解

Void_Trailwalker · 2024-12-28 16:29:08 · 题解

先放代码：

#include<iostream>
#include<cmath>
using namespace std;
unsigned long long n , a[100005] , T , k;
int main(){
    cin >> T;
    while(T--){
        cin >> n >> k;
        unsigned long long maxn = 0;
        for(int i=1;i<=n;i++){
            cin >> a[i];
            maxn = max(maxn,a[i]);
        }
        if(k==0){
            maxn = 0;unsigned long long ans = 0;
            for(int i=1;i<=n;i++){
                maxn = max(maxn,a[i]);
                ans += maxn;
            }
            cout << ans << endl;
        }else{
            if(n>2||(k%2==1&&a[1]<=a[2])||(k%2==0&&a[1]>=a[2]))cout << maxn * n << endl;
            else{
                if(a[1]>a[2]){
                    if(k%2==0)cout << a[1] * 2 << endl;
                    else cout << a[1] + a[2] << endl;
                }
                else{
                    if(k%2==0)cout << a[1] + a[2] << endl;
                    else cout << a[1] + a[2] << endl;
                }
            }
        }
    }
    return 0;
}

解释：
对于每朵花，不难发现我们将美丽度最大的花交换到最前面，答案即为最大的。所以我们只需要将最大的花交换到最前面，然后其余操作可以无视。
注意：
如果 n 等于 2，或 k 等于 0，我们需要特判一下，详见代码。