题解：P13750 [NWERC 2024] Limited Library

veni_vedi_veci · 2026-04-25 14:16:05 · 题解

传送门

P13750 [NWERC 2024] Limited Library

题意

现在有 n 层书架，每层最多可放 x 本书，又有 m 本新书要放进书架里，且在放书时放的书的高度不得超过该层书架高度。

同时我们希望能放更多艺术品，每层最多放 1 个艺术品，且只有当该层旁边最多有 y 本书时，艺术品才能放下。

求在能够放下所有新书的前提下，最多能放多少艺术品，若新书都无法放完，则输出 impossible。

思路

因为求的是放的艺术品数，所以可以用二分来求艺术品数（因为若放 k 个艺术品可行，那么放更少的留的空间还会更大，一样可行，满足二分单调性）。

而且因为每层能放的书的数量是一样的，矮书既能放高层又能放矮层，但高书只能放高层，所以最优策略为矮书放矮层，高书放高层。

同理，艺术品放矮层比放高层也要更优。

所以先对每本书和每层书架的高度都升序排序。

接着二分答案，check 中在前 mid 层放 y 本书，其他层放 x 本书，最后看是否放完所有书即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,x,y,l,r,ans=-1;//先为答案赋值为 -1，若最后还是 -1 则表示一直都没合法过，输出 impossible
vector<int> a,b;
bool check(int k)
{
    int j=0;
    for(int i=0;i<k&&j<m;i++)//在前 mid 层放 y 本书 
    {
        int cnt=y;
        while(cnt--&&j<m&&b[j]<=a[i])
            j++;
    }
    for(int i=k;i<n&&j<m;i++)//在其他层放 x 本书
    {
        int cnt=x;
        while(cnt--&&j<m&&b[j]<=a[i])
            j++;
    }
    return j>=m;//判断书是否放完
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>x>>y;
    r=n;
    a.resize(n);
    b.resize(m);
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<m;i++)
        cin>>b[i];
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());//排序
    while(l<=r)//二分答案
    {
        int mid=(l+r)>>1;
        if(check(mid))
            ans=mid,l=mid+1;
        else 
            r=mid-1;
    }
    if(ans==-1)//一直都放不完
        cout<<"impossible";
    else
        cout<<ans;
    return 0;
}