算法标签：

搜索

题解：

学习了大佬博客 难度比较大，需要枚举很多种情况，对思维的全面性要求高 就是在题目所给的木板上所有的位置，让你放进一本古书，

这本书有厚度和高度，所以你放的时候必须竖着放，而且不能有木板挡着它。

然后如果有挡着书的木板可以有6种操作：

1、不动

2、左右移动，重心必须在两个栓子之间。

3、通过锯一段木板。

4、通过拔掉栓子，左右移动

5、移动栓子 和 锯木板 同时实现。

6、把栓子和木板都撤了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int xn, yyn, xt, yt, n;
//壁龛的宽度高度、旧书的宽度和高度、货架的数量 
int mindz = INF, minmb = INF; //最少钉子，最少木板 
struct node {
    int x, y, l, x1, x2;
    //左端距离、高度、长度、左端和左支撑钉距离、左端和右支撑点的距离 
    friend bool operator <(node a, node b) {
        return a.y < b.y; //重载小于号，用来排序 
    }
}p[105];

void move(int k, int x, int &dz, int &mb) {
    for (int i = k + 1; i <= n; i++) //木板是有序的，故在枚举完在第k个木板上放书后，要判断k以上的木板是否会阻挡书的放置 
    {
        if (p[i].y >= p[k].y + yt) break; //以上的都挨不到书了
        if (p[i].x + p[i].l <= x || p[i].x > x + xt) continue; //此木板不会对书架造成影响
        if (p[i].x2 <= x) //此木板右钉子在起始点左端 
        {
            int lst; //注意，可以通过左移来避免对书架造成影响
            if (x <= 2 * p[i].x1) //要考虑重心的问题
                lst = 2 * (x - p[i].x1);
            else
                lst = x;
            if (lst < p[i].l) mb += p[i].l - lst;
        }
        else if (p[i].x1 >= x + xt) //木板左钉子在终点的右端 
        {
            int lst; //与上种情况同理
            if (p[i].x2 - x - xt <= xn - p[i].x2)
                lst = 2 * (p[i].x2 - x - xt);
            else lst = xn - x - xt;
            if (lst < p[i].l) mb += p[i].l - lst;
        }
        else if (p[i].x1 <= x && p[i].x2 > x && p[i].x2 < x + xt) //起始点钉子在钉子之间且终点在右钉子右边 
        {
            if (x == 0) //若起始点为0，只能删掉一整条边 
            {
                dz += 2;
                mb += p[i].l;
            }
            else //移钉 
            { //注意：对于此情况，是将木板靠到最左边，最右的部分截掉 
                dz++;
                if (p[i].l > x) mb += p[i].l - x; //截木板 
            }
        }
        else if (p[i].x1 > x && p[i].x1 < x + xt && p[i].x2 >= x + xt) //左钉子在起始点与终点之间并且右钉子在终点的右端 
        {
            if (x + xt == xn) //若终点到右端了，只能删除一整条边 
            {
                dz += 2;
                mb += p[i].l;
            }
            else //移钉 
            { //注意：对于此情况，是将木板靠到最右边，最左的部分截掉 
                dz++;
                if (p[i].l > xn - x - xt) mb += p[i].l - xn + x + xt; //截木板 
            }
        }
        else if (p[i].x1 <= x && p[i].x2 >= x + xt) //两钉子在起点终点的两端之外 
        {
            if (x == 0 && xt == xn) //只能全拆掉 
                dz += 2;
            else dz++;
            int lst = max(x, xn - x - xt);
            if (p[i].l > lst)
                mb += p[i].l - lst;
        }
        else if (p[i].x1 > x && p[i].x2 < x + xt) //不多想直接拆 
        {
            dz += 2;
            mb += p[i].l;
        }
    }
}

void solve(int k) {
    for (int i = 0; i <= xn - xt; i++) //枚举书的起始位置 
    {
        int dz = 0, mb = 0;
        if (i + p[k].l < p[k].x1) continue; //木板根本放不到钉子上，continue
        if (2 * (p[k].x1 - i) > p[k].l || //重心出界（左钉子）
            2 * (i + xt - p[k].x2) > p[k].l || //重心出界（右钉子）
            p[k].x2 - i > p[k].l || //木板长度不够（左端点到右钉子距离超过了木板长度） 
            i + xt - p[k].x1 > p[k].l) //木板长度不够（右端点到左钉子距离超过了木板长度)
            dz++;
        move(k, i, dz, mb);
        if (dz < mindz || (dz == mindz && mb < minmb))
            mindz = dz, minmb = mb;
    }
}

int main() {
    cin >> xn >> yyn >> xt >> yt;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].y >> p[i].x >> p[i].l >> p[i].x1 >> p[i].x2;
        p[i].x1 += p[i].x; //左墙与最左端钉子 
        p[i].x2 += p[i].x; //左墙与最右端钉子 
    }
    sort(p + 1, p + n + 1); //按照书架的高度从低到高排序 
    for (int i = 1; i <= n; i++) {
        if (p[i].y + yt > yyn) break; //若第i个书架的高度加上书的高度大于最大高度
        //书无法放在i以后的任何一个书架上，直接break
        if (p[i].l >= xt) solve(i);
        //若第i个书架可以放得下最大的那本书，则开始找其最小耗费 
    }
    cout << mindz << " " << minmb;
    return 0;
}

🧠 题解（Solution）

这是一道二维空间可行区间搜索+优化决策问题，带有较强工程模拟性质。

🎯 目标：

使古籍可以放入某一层书架上方，并且满足：

放下的垂直空间 $\geq YT$；

放下的水平空间 $\geq XT$；

替换或调整的书架尽量少移动支撑钉子；

如有多种方案，进一步最小化削减木板总长度。

✅ 解题思路：

预处理所有书架信息，包括其覆盖的水平区间、支撑钉的实际位置等；

枚举每一个书架作为“承放古籍的层”：

上方空间是否 $\geq YT$；

在其上方的所有书架中，判断哪些会阻碍古籍（与古籍的水平区域有重叠）；

对所有阻碍的书架考虑六种操作策略（操作 $1-6$）：

判断每种操作是否能让该书架让出空间；

计算每种策略的代价（钉子移动数 + 木板削减长度）；

对每个候选承载书架，累加其上方所需调整的总代价，选取：

钉子移动数最少的方案；

在上述基础上削减长度最小的。

✅ 技术点：

利用区间重叠判定来识别哪些书架影响目标区域；

钉子支持合法性需动态校验；

支持操作模拟及代价评估（钉子变动、木板裁剪）；

贪心 + 枚举所有备选方案中代价最小的。

代码实现：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
int Xn,Yn,Xt,YT,n;
struct node
{
    int h,x,len,l,r;
}P[105];
struct ANS
{
    int move,cut;
};
bool comp(node a,node  b)
{
    return a.h<b.h;
}
ANS _clear(int k,int p,int base)
{
    ANS t={0,0};t.move=base;
    //cout<<p<<" "<<base<<endl;
    //cout<<t.cut<<" "<<t.move<<endl;
    int a,b,c,d,e;
    int left=p,right=p+Xt;
    //cout<<endl;
    for(a=k+1;a<=n;a++)
    {
        
        if(P[a].h>=P[k].h+YT)break;
        int pos1=P[a].x;int pos2=P[a].x+P[a].len;
        if(pos1>=right||pos2<=left)continue;
        //cout<<t.cut<<" "<<endl; 
        if(P[a].r<=left)
        {
            if(P[a].len>left)
            {
                t.cut+=P[a].len-left;
                if(left-P[a].l<P[a].l)t.cut+=(2*P[a].l-left);
            }
            else
            {
                if(2*(left-P[a].l)<P[a].len)t.cut+=(P[a].len-2*(left-P[a].l));
            }
        }
        else if (P[a].l>=right)
        {
            if(P[a].len>Xn-right)
            {
                t.cut+=(P[a].len+right-Xn);
                if(P[a].r-right<Xn-P[a].r)t.cut+=(Xn+right-2*P[a].r);
            }
            else
            {
                if(2*(P[a].r-right)<P[a].len)t.cut+=(P[a].len-2*(P[a].r-right));
            }
        }
        else if(P[a].l<=left&&right<=P[a].r)
        {
            t.move++;
            if(left>=P[a].len)continue;
            if(Xn-right>=P[a].len)continue;
            if(left==0&&right==Xn)
            {
                t.move++;
                t.cut+=P[a].len;
                continue;
            }
            if(left==0)
            {
                t.cut+=(P[a].len-(Xn-right));
                continue;
            }
            if(right==Xn)
            {
                t.cut+=(P[a].len-left);
                continue;
            }
            t.cut+=min((P[a].len-Xn+right),(P[a].len-left));
        }
        else if(P[a].l<=left&&left<=P[a].r&&P[a].r<=right)
        {
            t.move++;
            if(left>=P[a].len)continue;
            if(left==0)
            {
                t.move++;
                t.cut+=P[a].len;
            }
            else
            {
                t.cut+=(P[a].len-left);
            }
        }
        else if(left<=P[a].l&&P[a].l<=right&&right<=P[a].r)
        {
            t.move++;
            if(Xn-right>=P[a].len)continue;
            if(right==Xn)
            {
                t.move++;
                t.cut+=P[a].len;
            }
            else
            {
                t.cut+=(P[a].len-Xn+right);
            }
        }
        else if(left<=P[a].l&&P[a].r<=right)
        {
            t.move+=2;
            t.cut+=P[a].len;
        }
    }
    //cout<<t.cut<<" "<<t.move<<" "<<k<<" "<<p<<endl;
    return t;
}
ANS _try(int k)
{
    ANS ans={999999999,999999999};
    if(P[k].len<Xt||P[k].h+YT>Yn)return ans;
    int a,b,c,d;
    //printf("%d %d\n",ans.cut,ans.move);
    for(a=0;a+Xt<=Xn;a++)
    {
        //cout<<a<<endl;
        ANS t;
        t.cut=0;t.move=0;
        if(a+P[k].len<P[k].l)continue;
        if(a+Xt-P[k].len>P[k].r)break;
        if(P[k].len>=(P[k].r-P[k].l)*2)
        {
            if((P[k].l-a)*2>P[k].len||(a+Xt-P[k].r)*2>P[k].len)t.move++;
        }
        else
        {
            if((P[k].r-a)>P[k].len||a+Xt-P[k].l>P[k].len)t.move++;
        }    
        t=_clear(k,a,t.move);    
        if(t.move<ans.move)ans=t;
        else if(t.move==ans.move&&t.cut<ans.cut)ans=t;
    }
    return ans;
}
int main()
{
    scanf("%d%d%d%d%d",&Xn,&Yn,&Xt,&YT,&n);
    int a,b,c,d,e;
    for(a=1;a<=n;a++)
    {
        scanf("%d%d%d%d%d",&P[a].h,&P[a].x,&P[a].len,&P[a].l,&P[a].r);
        P[a].l+=P[a].x;
        P[a].r+=P[a].x;
    }
    sort(P+1,P+n+1,comp);
    /*for(a=1;a<=n;a++)
{
    printf("%d %d %d %d %d\n",P[a].h,P[a].x,P[a].len,P[a].l,P[a].r);;
    }*/
    ANS ans;ANS t;
    ans.move=999999999;ans.cut=999999999;
    for(a=1;a<=n;a++)
    {
        if(P[a].h+YT>Yn)break;
        t=_try(a);
        if(t.move<ans.move)ans=t;
        else if(t.move==ans.move&&t.cut<ans.cut)ans=t;
    }
    printf("%d %d",ans.move,ans.cut);
    return 0;
}