程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 5493 Queue（二分+樹狀數組）

HDU 5493 Queue（二分+樹狀數組）

編輯：關於C++

題意：有n個人排隊，每個人都有一個獨一無二的身高，告訴你每個人的身高和他前面或者後面的比他高的人的個數（到底是前是後是未知的）。要求你還原原來的隊列，並且字典序最小。

思路：因為要求字典序最小，我們可以先按照身高從小到大排序，假設當前到了第i高的人，他前面或者後面有k個人，那麼他前面的所有人都比他矮，比他高的還有n-i個人，那麼假設他前面還有p個空位，他就是第p+1個空位上的人，那麼怎麼求p呢？因為要求字典序最小，所以 p = min(k, n - i - k)。為什麼這樣是對的呢？每個人有兩個可能位置啊，因為他之前的都比他矮，所以他無論在哪個位置都是可以的。那麼為了讓字典序最小，就選擇一個較小的位置。當n - i - k < 0 時，說明沒有多余空格，那麼無解。

為了加速算法，二分第i個人的位置，用樹狀數組判斷他前面有多少人以此確定空余的位置數。

復雜度O(n*logn*logn)。

細節參見代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 100000 + 5;
int T,n,m,bit[maxn],kase=0,ans[maxn];
struct node {
    int v, num;
    bool operator < (const node& rhs) const {
        return v < rhs.v;
    }
}a[maxn];
int sum(int x) {
    int ans = 0;
    while(x > 0) {
        ans += bit[x];
        x -= x & -x;
    }
    return ans;
}
void add(int x, int d) {
    while(x <= n) {
        bit[x] += d;
        x += x & -x;
    }
}
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        memset(bit, 0, sizeof(bit));
        for(int i=1;i<=n;i++) {
            scanf("%d%d",&a[i].v,&a[i].num);
        }
        sort(a+1,a+n+1);
        bool ok = true;
        for(int i=1;i<=n;i++) {
            int k = min(a[i].num, n-i-a[i].num);
            int l = 1, r = n, mid;
            if(n - i - a[i].num < 0) { ok = false; break; }
            ++k;
            while(r > l) {
                mid = (r+l)/2;
                if(mid - sum(mid) >= k) r = mid;
                else l = mid + 1;
            }
            add(l, 1);
            ans[l] = a[i].v;
        }
        printf("Case #%d:",++kase);
        if(ok) {
            for(int i=1;i<=n;i++) {
                printf(" %d",ans[i]);
            }
            printf("\n");
        }
        else printf(" impossible\n");
    }
    return 0;
}