牛客2020寒假训练营6-C

七月 15, 2020

题意

现在你有 N 块矩形木板，第 i 块木板的尺寸是 Xi*Yi，你想用这些木板来玩汉诺塔的游戏。
我们知道玩汉诺塔游戏需要把若干木板按照上小下大的顺序堆叠在一起，但因为木板是矩形，所以有一个问题：
第 i 块木板能放在第 j 块木板上方当且仅当 Xi<Xj 且 Yi<Yj，于是你很可能没法把所有的木板按照一定的次序叠放起来。
你想把这些木板分为尽可能少的组，使得每组内的木板都能按照一定的次序叠放。
你需要给出任意一种合理的分组方案。
提醒：“任意”意味着你的答案不必和标准输出完全一致，只要正确即可。

第一行，一个正整数 N
接下来 N 行，每行两个正整数表示 Xi 和 Yi
对于所有的数据，1≤N≤100,000，1≤Xi,Yi≤N，Xi 互不相等且 Yi 互不相等

输出文件包含两行，第一行一个正整数，表示最少组数
第二行 N 个正整数，依次表示你的方案中每块木板分在了哪一组
组的编号必须是从 1 开始的连续整数

已知
Dilworth 定理
一个序列最少可以分成n个上升子序列,这个序列最长不上升子序列长度为m,则n=m
一个序列最少可以分成n个下降子序列,这个序列最长不下降子序列长度为m,则n=m
链的最少划分数=反链的最长长度

举栗子就是:

上升子序列(<)的反链是原序列的最大不上升子序列(=>),,,

下降子序列(>)的反链就是原序列的最大不下降子序列(<=)

记住不要漏等号

对于本题
将木板按照Xi从小到大排序，将这时的Yi数列记为Zi数列，则问题变成将Zi划分为尽可能少的若干组上升子序列。
根据Dilworth定理，最小组数等于Zi的最长不上升子序列长度。
用二分栈优化dp Onlogn 找到Zi数列的最长不上升子序列并更新每组的最长上升子序列

具体的开一个数组lis已经记录到第i个数时能构成的最长非上升子序列
从前到后遍历Zi 在lis中二分寻找第一个小于等于Zi的数用Zi替换这个数使得最终lis是最长的非上升子序列
而这个替换的数取代在lb位置上的数实际上就是在原先的那组板子上叠最长上升子序列
二分细节见代码

详见：此处
举例用二分栈优化最长上升子序列dp

开一个栈，每次取栈顶元素top和读到的元素temp做比较，如果temp > top 则将temp入栈；如果temp < top则二分查找栈中的比temp大的第1个数，并用temp替换它。最长序列长度即为栈的大小top。

这也是很好理解的，对于x和y，如果x < y且Stack[y] < Stack[x],用Stack[x]替换Stack[y]，此时的最长序列长度没有改变但序列Q的”潜力”增大了。

或者说开辟了一个新分支的同时不影响原来分支和最长子序列
详见：此处

举例：原序列为1，5，8，3，6，7

栈为1，5，8，此时读到3，用3替换5，得到1，3，8；再读6，用6替换8，得到1，3，6；再读7，得到最终栈为1，3，6，7。最长递增子序列为长度4。

# include<bits/stdc++.h>

using namespace std;
typedef long long ll;

# define endl '\n'

struct Data{
    int x,y;
    int indx;
}data[(int)1e5+5];
int lis[(int)1e5+5];
int ans[(int)1e5+4];
bool cmp(Data a,Data b){return a.x<b.x;}
int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++)cin>>data[i].x>>data[i].y,data[i].indx=i;
    sort(data,data+n,cmp);
    int len=0,lb,rb;
    lis[len]=data[0].y;
    ans[data[0].indx]=len;
    for(int i=1;i<n;i++){
        lb=0,rb=len;
        while(lb<=rb){
            int mid=(lb+rb)>>1;
            if(lis[mid]<data[i].y)rb=mid-1;
            else lb=mid+1;
        }
        len=max(len,lb);
        lis[lb]=data[i].y;
        ans[data[i].indx]=lb;///记录对应的每个木板放入哪一组 二分得到的lb实际表示分到哪一组
    }
    cout<<len+1<<endl;
    for(int i=0;i<n;i++)cout<<ans[i]+1<<" ";
}

查看评论