CF1668B题解

分析

阅读题目，很容易发现相邻两个人之间的座位数是两个人需求中较大的那一个，也就是 \(\max(a_i,a_{i-1})\)， 同时需要加上 \(a_n-a_1\) 。

但是单纯这个思路交上去会 WA ，于是我们再仔细读一遍题，发现题目并没有说保证输入有序，为了让 \(\sum ^{n-1} _{i=1} \max(a_i,a_{i-1}) + \max(a_1,a_n)\) 最小，我们需要先将 \(a\) 数组排序一次，升序和降序都可以。

code:

#include "stdio.h"
#include "algorithm"
using namespace std;

long long a[100005]={};

void wk() {
    long long n,m;
    scanf("%lld%lld",&n,&m);
    for(long long i=1;i<=n;++i) scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    long long ans=n;
    for(long long i=1;i<n;++i) ans+=max(a[i],a[i+1]);
    ans+=max(a[1],a[n]);
    if(ans<=m) printf("YES\n");
    else printf("NO\n");
}

signed main() {
    int t;
    scanf("%d",&t);
    while(t--) wk();
    return 0;
}