程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 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;
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved