题解 P4613 【[COCI2017-2018#5] Olivander】

· · 题解

闲来无聊刷红题。即然是一道红题应该都是我这样的蒟蒻在做吧题解就写得详细一点吧！

看到这种题目当然是直接丢给谷歌翻译喽~

题目大意：有n个物体和n个盒子给你每个物体的长度和每个盒子的长度判断能否将物体都装在盒子中（每个盒子只能装一个物体）。

思路：将物体和盒子的最大长度最小长度都记录下来。如果物体的最小长度大于盒子的最小长度则最小的盒子什么都放不进去输出NE，如果物体的最大长度大于盒子的最大长度则最大的物体放不进去输出NE。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n;
int g[1001],he[1001];
bool pd[10001];
int maxx1,minn1=0x7fffffff,maxx2,minn2=0x7fffffff;
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>g[i];
        maxx1=max(maxx1,g[i]);
        minn1=min(minn1,g[i]);
    }
    for(int i=1;i<=n;++i)
    {
        cin>>he[i];
        maxx2=max(maxx2,he[i]);
        minn2=min(minn2,he[i]);
    }
    if(maxx2<maxx1||minn2<minn1)
    {
        cout<<"NE";
        return 0;
    }
    cout<<"DA";
    return 0;
}

光进行这两种判断就可以的80分哦！ 正解思路：物体当然要放到比他大的最少的盒子里，这样大盒子才可以用来放大物体！ AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n;
int g[1001],he[1001];
bool pd[10001];
int maxx1,minn1=0x7fffffff,maxx2,minn2=0x7fffffff;
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>g[i];
        maxx1=max(maxx1,g[i]);
        minn1=min(minn1,g[i]);
    }
    for(int i=1;i<=n;++i)
    {
        cin>>he[i];
        maxx2=max(maxx2,he[i]);
        minn2=min(minn2,he[i]);
    }
    if(maxx2<maxx1||minn2<minn1)
    {
        cout<<"NE";
        return 0;
    }//以上为输入和两种判断。
    sort(g+1,g+1+n);
    sort(he+1,he+1+n);//sort是一个排序函数。
    int sum=0;//计数器。
    for(int i=1;i<=n;++i)//for物体长度。
    {
        for(int j=1;j<=n;++j)//因为排过序所以这样是盒子长度从小到大。
        {
            if(pd[j]==0&&he[j]>=g[i])//这个盒子没放过东西并且要大于等于物体长度。
            {
                sum++;//计数器加一。
                pd[j]=1;//这个盒子放过东西。
                break;
            }
        }
    }
    if(sum==n) cout<<"DA";//如果都放进去了输出DA否则输出NE
    else cout<<"NE";
    return 0;
}