P11309 纷飞的樱花雨-题解

AI_god · 2024-12-01 13:45:18 · 题解

题目传送门

题目大意

有一组樱花，你可交换刚好 k 次樱花掉落的顺序（也就是交换 a_x 和 a_y 的顺序），使樱花美丽总和最大。

每朵樱花掉落后，樱花掉落的总观赏度会增加这朵樱花及之前所有已经掉落的樱花的美丽度的最大值。

题目分析

我们只要让第一次掉落的樱花是美丽值最大的就行，因为这样可以让以后每次加都可以加最大值。

怎么做呢？这里先分为两种情况来讨论。

long long sum=0,y=0;
for(int j=1;j<=n;j++){
  cin>>a[j];
  if(a[j]>y){
    y=a[j];
  }
  sum+=y;
}

剩下的为 k>0 的情况：

这里还要分两种情况来讨论：

• 然后是 n=2：因为题目保证 n 一定大于等于 2，所以这里只用考虑 n=2 的情况：这里就两种情况：第一朵的美丽度最大和第二朵的美丽度最大，首先假设第一朵的美丽度最大，若果交换的次数是偶数，那么交换完的第一朵的美丽度一定是最大的，这里直接输出 a_1 \times 2 就行，反之第二朵的美丽度最大：如果交换的次数是奇数，那么就一定可以使第二朵交换到第一朵的位置，然后直接输出 a_2 \times 2 就行，如果以上条件都不满足，则判断 k 为偶数：代表交换完之后位置不变，则输出 cout<<a[1]+max(a[1],a[2])<<endl;，否则 k 为奇数，代表交换完之后位置变化了，则输出 cout<<a[2]+max(a[1],a[2])<<endl;。

到这里思路就结束了，这就是这道题目的完整细节思路，希望管理能给过，最后附上 AC 代码：

AC 代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[10000105],t,k;
int main(){
    cin>>t;
    for(int i=1;i<=t;i++){
        cin>>n>>k;
        long long sum=0,y=0;
        for(int j=1;j<=n;j++){
            cin>>a[j];
            if(a[j]>y){
                y=a[j];
            }
            sum+=y;
        }
        if(k==0){
            cout<<sum<<endl;
            continue;
        }
        if(n>2||(k%2==0&&a[1]>=a[2])||(k%2==1&&a[1]<=a[2])){
            sort(a+1,a+1+n);
            cout<<a[n]*n<<endl;
        }
        else{
            if(k%2==0)cout<<a[1]+max(a[1],a[2])<<endl;
            if(k%2==1)cout<<a[2]+max(a[1],a[2])<<endl;
        }
    }
    return 0;
}

提交记录：R192243700 记录详情。