题解：P13700 [NWERC 2023] Arranging Adapters

· · 题解

P13700 [NWERC 2023] Arranging Adapters

思路

这是一个典型的贪心算法，需要优先插入长度较短的充电线，直到插座满了或充电线没有了为止。模拟就好了

AC代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5*2+10;
int v[N];
int n,s;
int ans=-1;
int x=0,y=0;
signed main(){
    cin>>n>>s;
    s--;
    for(int i=1;i<=n;++i) cin>>v[i];
    sort(v+1,v+n+1);
    if(s!=0){
        for(int i=1;i<=n;i++){
            s-=v[i]/3;
            ans++;
            if(v[i]%3==1) x++;
            else if(v[i]%3==2) y++;
            int tmp=0;
            if(x>=y) tmp=y+(x-y+1)/2;
            else tmp=y;
            if(tmp>=s) break;
        }
    }
    cout<<ans<<'\n';
    return 0;
}