题解：P10709 [NOISG2024 Prelim] Party

zhuxiangrui_2010 · 2024-07-07 17:58:30 · 题解

感谢DFs_YYDS和I_am_Kun的提醒，错误已改正。

题意

James 有 n 个朋友、n 个座位，两个朋友不能坐在相邻的座位上，选择其中任意个朋友，求每个朋友产生的快乐值 a_i 之和的最大值。

思路

因为两个朋友不能坐在相邻的座位上，所以 n 个座位可以坐 \left \lfloor \frac{n+1}{2} \right \rfloor 个人。

由于希望总快乐值最大，所以每个朋友产生的快乐值 a_i 都应该取较大的。可以进行排序由大到小进行取值且 a_i \le 0 时不取，易证得此时总快乐值最大。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[10000001],s=0;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=n;i>n/2;i--){
        if(a[i]<=0){
            break;
        }
        s+=a[i];
    }
    cout<<s;
    return 0;
}

完结撒花~