题解 P2859 【[USACO06FEB]摊位预订Stall Reservations】

c2020HXW · 2019-10-08 19:34:00 · 题解

我选择，模拟！！

因为此题时间段A和B的范围都可以承受，（太大了也可以离散化），不妨以时间为序来模拟这个简单过程

直接开一个栈，依次加入N-->1,表示要用的牛棚的编号（最多会用n个）

对于每一头牛，用类似前向星链表的方式在他起点的时间加一个编号为i的儿子

同理，在结束位置也加一个编号为i的儿子（用另一套链表）

然后就按照时间顺序简单模拟：

不管啥的先读进来加入链表

对于每一个时间点

1.从链表取出在当时要牛棚的牛，把栈顶的牛棚给他：

2.ans与已经拿去用的牛棚数量（就是(n-top) )取max;

3.从链表取出当时要离开牛棚的牛，把该牛用的牛棚（就是ans[i]）塞回栈顶

然后输出，快乐的结束！

code:

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
//#define int long long
const int Maxx=1000005,Maxn=2001,INF=0x3f3f3f3f,Mod=1e9+7;
inline int read()
{
    int res=0,bj=0;char ch=getchar();
    while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
    return bj?-res:res;
}
void print(int x)
{
    if(x>9)print(x/10);
    putchar(x%10^48);
}
inline void printnum(int x,char ch)
{
    if(x<0)putchar('-'),x=-x;
    print(x),putchar(ch);
}
int n,x,y,tp,ans,sum,Maxnum=-INF,Minnum=INF,stk[Maxx],as[Maxx];
int hx[Maxx],nx[Maxx],hy[Maxx],ny[Maxx];
signed main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    n=read();
    for(int i=1;i<=n;i++)
    {
        Minnum=min(Minnum,x=read());
        Maxnum=max(Maxnum,y=read());
        nx[i]=hx[x],hx[x]=i;
        ny[i]=hy[y],hy[y]=i;
        //读入，加入链表，因为如果按邻接表的来，to[i]=i,于是就干脆把to[]省了…… 
        stk[i]=(n-i+1);
    }tp=n;
    for(int i=Minnum;i<=Maxnum;i++)
    {
        for(int j=hx[i];j;j=nx[j])as[j]=stk[tp--];
        ans=max(ans,n-tp);
        for(int j=hy[i];j;j=ny[j])stk[++tp]=as[j];
    }
    printnum(ans,'\n');
    for(int i=1;i<=n;i++)printnum(as[i],'\n');
    return 0;
}