2012-09-26 21:01:05Morris
[ZJ][heap+計算] a373. 賽車
內容 ：
有n輛賽車，從各不相同的位置出發，以各種速度開始往右行駛，不斷有超車現象發生
給定n輛賽車的出發位置Xi與速度Vi，請輸出超車事件的總數，以及依序列出最早發生的超車事件。
若有兩個超車事件同時發生，請先輸出超車位置數值較小的。
輸入說明
：
第一列有一個正整數N (0< N <=250,000)
第二列開始有N列，每列包含兩個整數Xi和Vi代表第i輛車的初始位置與速度。
(0<=Xi<=1,000,000，0<Vi<=100，並且Xi依照嚴格遞增順序排列)
第二列開始有N列，每列包含兩個整數Xi和Vi代表第i輛車的初始位置與速度。
(0<=Xi<=1,000,000，0<Vi<=100，並且Xi依照嚴格遞增順序排列)
輸出說明
：
第一列請輸出超車事件總數除以1,000,000的餘數。
第二列開始請依序輸出超車事件。若全體的超車事件超過10,000個，那麼只要輸出前10,000個超車事件即可。
每一個超車事件可以用兩個數字表示i, j，代表i超越j。
範例輸入 ：
4 0 2 2 1 3 8 6 3
範例輸出 ：
2 3 4 1 2
提示
：
※測資保證不會有超車事件同時同地發生
出處
：
CEOI2003 The Race
(管理：david942j)
首先先不對序列做任何排序, 總之最後會依照速度由小排到大,
我們先將"鄰近對"的放入超車可能, 將這些對放入 heap 中,
不過要注意有可能從 heap 丟出的最小已經不存在了, 那麼要檢查是否是相鄰的,
最後在限定的 10000 次之後, 採用 Merge Sort 去計算剩餘的交換次數,
紀錄這個排序是要 Stable Sort, 因此判斷時要注意一下
首先先不對序列做任何排序, 總之最後會依照速度由小排到大,
我們先將"鄰近對"的放入超車可能, 將這些對放入 heap 中,
不過要注意有可能從 heap 丟出的最小已經不存在了, 那麼要檢查是否是相鄰的,
最後在限定的 10000 次之後, 採用 Merge Sort 去計算剩餘的交換次數,
紀錄這個排序是要 Stable Sort, 因此判斷時要注意一下
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef struct {
int x, v, i;
} Car;
typedef struct {
double t, s;
int a, b;
} ele;
struct cmp {
bool operator() (ele a, ele b) {
if(a.t != b.t)
return a.t > b.t;
return a.s > b.s;
}
};
Car A[250000], X[250000];
int ans;
void Merge(int l, int m, int r) {
int idx1 = l, idx2 = m+1, top = 0, i, j;
int D = 0;
while(idx1 <= m && idx2 <= r) {
if(A[idx1].v <= A[idx2].v)
X[top++] = A[idx1++], ans += D;
else
X[top++] = A[idx2++], D++;
if(ans >= 1000000) ans -= 1000000;
if(D >= 1000000) D -= 1000000;
}
while(idx1 <= m) {
X[top++] = A[idx1++], ans += D;
if(ans >= 1000000)
ans -= 1000000;
}
while(idx2 <= r) X[top++] = A[idx2++], D++;
for(i = 0, j = l; i < top; i++, j++)
A[j] = X[i];
}
void Msort(int l, int r) {
if(l < r) {
int m = (l+r)>>1;
Msort(l, m);
Msort(m+1, r);
Merge(l, m, r);
}
}
int main() {
int n, i;
int wh[250000];
while(scanf("%d", &n) == 1) {
for(i = 0; i < n; i++) {
scanf("%d %d", &A[i].x, &A[i].v);
A[i].i = i;
wh[i] = i;
}
ele E, T;
priority_queue<ele, vector<ele>, cmp> Q;
for(i = 1; i < n; i++) {
if(A[i-1].v > A[i].v) {
E.a = A[i-1].i, E.b = A[i].i;
E.t = (double)(A[i].x - A[i-1].x)/(A[i-1].v - A[i].v);
E.s = A[i].x + E.t*A[i].v;
Q.push(E);
}
}
int cnt = 0, Ea[10000], Eb[10000];
while(cnt < 10000 && !Q.empty()) {
E = Q.top();
Q.pop();
if(wh[E.a]+1 == wh[E.b]) {
Ea[cnt] = E.a+1, Eb[cnt] = E.b+1;
cnt++;
i = wh[E.a];
swap(A[wh[E.a]], A[wh[E.b]]);
wh[A[i].i] = i, wh[A[i+1].i] = i+1;
i = wh[E.b];
if(i-1 >= 0 && A[i-1].v > A[i].v) {
T.a = A[i-1].i, T.b = A[i].i;
T.t = (double)(A[i].x - A[i-1].x)/(A[i-1].v - A[i].v);
T.s = A[i].x + T.t*A[i].v;
Q.push(T);
}
i = wh[E.a];
if(i+1 < n && A[i].v > A[i+1].v) {
T.a = A[i].i, T.b = A[i+1].i;
T.t = (double)(A[i+1].x - A[i].x)/(A[i].v - A[i+1].v);
T.s = A[i].x + T.t*A[i].v;
Q.push(T);
}
}
}
ans = 0;
Msort(0, n-1);
ans += cnt;
printf("%d\n", ans);
for(i = 0; i < cnt; i++)
printf("%d %d\n", Ea[i], Eb[i]);
}
return 0;
}