题解：P14702 [ICPC 2024 Tehran R] Boat

Hcy114514 · 2025-12-11 14:22:57 · 题解

首先特判 n=1 的情况。

先按体重从小到大排序。不难发现，最佳方案应该是将前 x(a_1+a_x \le n) 人和第一个人一起坐船过去，然后第一个人回来，一共 2 步。

剩下的人单独坐船过去，第二个人单独回来，第一个人再把第二个人送回去，最后第一个人回来，一共 4 步。所以总步数即为 x\times 2-2+(n-x)\times 4-1。

那么什么时候无解呢？如果第一个人和第二个人的体重之和大于 w，此时就是无解的。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,w,x=2,a[1145];
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return x*f;
}
signed main(){
    n=read();w=read();
    for(int i=1;i<=n;i++)a[i]=read();a[n+1]=1114514;
    sort(a+1,a+n+1);
    if(n==1||a[n]>w)cout<<(a[n]>w?-1:1),exit(0);
    for(;a[x]+a[1]<=w;)x++;x--;
    if(x==1)cout<<-1,exit(0);
    if(x==n)cout<<n+n-3,exit(0);
    cout<<x*2-2+(n-x)*4-1;
    return 0;
}