2020牛客寒假算法基础集训营6_C 汉诺塔（思维、dp）

题目大意

题目链接

跟你n个(x, y) 每一组， 都满足x_i < x_i + 1 && y_i < y_i + 1，问如何尽可能分更少的组， 输出每一个分到第几组（组号从1开始）

分析

按x从小到大排序。

Dilworth定理： 最小组数等于y的最长下降子序列长度

最长下降子序列 用二分优化的dp求法中， dp[i]表示长度为i的最长下降子序列的最后一个数， 显然， 我们dp[i]越大越好， 当前为a[i] 所以我们就用二分找到dp数组中第一个比a[i]小的数(位置为cnt)， 如果有， 就把dp[cnt] = a[i] ，， 如果没有， cnt = ++len dp[cnt] = a[i] 同时， a[i]所对应的原下标对应的组数 就是 cnt.

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 5;

inline ll read() {
    ll res = 0;bool f = 0;char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = 1;ch = getchar();}
    while (ch <= '9' && ch >= '0') {res = (res << 3) + (res << 1) + ch - '0';ch = getchar();}
    return f ? (~res + 1) : res;
}

struct node{
    int x, y, id;
    bool operator < (const node &c) {return x < c.x;}  // 按x从小到大排序
}a[N];
int f[N], ans[N], n;
int main(){
    n = read();
    for (int i = 1; i <= n; ++i) a[i].x = read(), a[i].y = read(), a[i].id = i;
    sort(a + 1, a + 1 + n);
    int len = 1;
    for (int i = 1; i <= n; ++i){
        int low = 1, high = len, mid;
        while(low < high){
            mid = low + (high - low) / 2;
            if (f[mid] < a[i].y) high = mid;
            else low = mid + 1;
        }
        if (f[low] >= a[i].y) low = ++len; // 如果没有找到 
        f[low] = a[i].y;
        ans[a[i].id] = low;
    }
    cout << len << "\n";
    for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
    return 0;
}

恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan

千万不要图快——如果没有足够的时间用来实践， 那么学得快， 忘得也快。