Description
最近，阿Q開了一間寵物收養(yǎng)所。收養(yǎng)所提供兩種服務：收養(yǎng)被主人遺棄的寵物和讓新的主人領養(yǎng)這些寵物。每個領養(yǎng)者都希望領養(yǎng)到自己滿意的寵物，阿Q根據(jù)領養(yǎng)者的要求通過他自己發(fā)明的一個特殊的公式，得出該領養(yǎng)者希望領養(yǎng)的寵物的特點值a（a是一個正整數(shù)，a<2^31），而他也給每個處在收養(yǎng)所的寵物一個特點值。這樣他就能夠很方便的處理整個領養(yǎng)寵物的過程了，寵物收養(yǎng)所總是會有兩種情況發(fā)生：被遺棄的寵物過多或者是想要收養(yǎng)寵物的人太多，而寵物太少。 1． 被遺棄的寵物過多時，假若到來一個領養(yǎng)者，這個領養(yǎng)者希望領養(yǎng)的寵物的特點值為a，那么它將會領養(yǎng)一只目前未被領養(yǎng)的寵物中特點值最接近a的一只寵物。（任何兩只寵物的特點值都不可能是相同的，任何兩個領養(yǎng)者的希望領養(yǎng)寵物的特點值也不可能是一樣的）如果有兩只滿足要求的寵物，即存在兩只寵物他們的特點值分別為a-b和a+b，那么領養(yǎng)者將會領養(yǎng)特點值為a-b的那只寵物。 2． 收養(yǎng)寵物的人過多，假若到來一只被收養(yǎng)的寵物，那么哪個領養(yǎng)者能夠領養(yǎng)它呢？能夠領養(yǎng)它的領養(yǎng)者，是那個希望被領養(yǎng)寵物的特點值最接近該寵物特點值的領養(yǎng)者，如果該寵物的特點值為a，存在兩個領養(yǎng)者他們希望領養(yǎng)寵物的特點值分別為a-b和a+b，那么特點值為a-b的那個領養(yǎng)者將成功領養(yǎng)該寵物。 一個領養(yǎng)者領養(yǎng)了一個特點值為a的寵物，而它本身希望領養(yǎng)的寵物的特點值為b，那么這個領養(yǎng)者的不滿意程度為abs(a-b)。【任務描述】你得到了一年當中，領養(yǎng)者和被收養(yǎng)寵物到來收養(yǎng)所的情況，希望你計算所有收養(yǎng)了寵物的領養(yǎng)者的不滿意程度的總和。這一年初始時，收養(yǎng)所里面既沒有寵物，也沒有領養(yǎng)者。 Input
第一行為一個正整數(shù)n，n<=80000，表示一年當中來到收養(yǎng)所的寵物和領養(yǎng)者的總數(shù)。接下來的n行，按到來時間的先后順序描述了一年當中來到收養(yǎng)所的寵物和領養(yǎng)者的情況。每行有兩個正整數(shù)a, b，其中a=0表示寵物，a=1表示領養(yǎng)者，b表示寵物的特點值或是領養(yǎng)者希望領養(yǎng)寵物的特點值。（同一時間呆在收養(yǎng)所中的，要么全是寵物，要么全是領養(yǎng)者，這些寵物和領養(yǎng)者的個數(shù)不會超過10000個） Output
僅有一個正整數(shù)，表示一年當中所有收養(yǎng)了寵物的領養(yǎng)者的不滿意程度的總和mod 1000000以后的結(jié)果。 Sample Input 5
0 2
0 4
1 3
1 2
1 5
Sample Output 3
(abs(3-2) + abs(2-4)=3，最后一個領養(yǎng)者沒有寵物可以領養(yǎng))
方法1： 直接上Splay。。。。。。。這個Splay我調(diào)了一個下午，原因是我開始插入兩個值-inf和inf的時候inf在用set寫的時候?qū)懗闪薕x7fffffff，直接溢出錯誤，我一直以為Splay寫錯了，改了一下午，簡直不要太傷。
#include <bits/stdc++.h>using namespace std;const int maxn = 100010;const int mod = 1000000;const int inf = 1e9;namespace SplayTree{ int siz[maxn], fa[maxn], val[maxn]; int ch[maxn][2], root, tot, ans; void newnode(int &rt, int father, int k){ rt = ++tot; siz[rt] = 1, fa[rt] = father; val[rt] = k; ch[rt][0] = ch[rt][1] = 0; } void pushup(int rt){ int l = ch[rt][0], r = ch[rt][1]; siz[rt] = siz[l] + siz[r] + 1; } void rotate(int x){ //旋轉(zhuǎn)，把x轉(zhuǎn)到根節(jié)點,kind為1代表右旋,kind為0代表左旋 int y = fa[x], kind = ch[y][1] == x; ch[y][kind] = ch[x][!kind]; fa[ch[y][kind]] = y; ch[x][!kind] = y; fa[x] = fa[y]; fa[y] = x; ch[fa[x]][ch[fa[x]][1] == y] = x; pushup(y), pushup(x); } void splay(int x, int goal) //伸展操作,把根為r的子樹調(diào)整為goal { while(fa[x] != goal) { int y = fa[x], z = fa[y]; if(z == goal) rotate(x); else if((ch[y][1] == x) == (ch[z][1] == y)) rotate(y), rotate(x); else rotate(x), rotate(x); } if(goal == 0) root = x; } int getPRe(int x){ //求前驅(qū) int t = ch[x][0]; while(ch[t][1]) t = ch[t][1]; return t; } int getsub(int x){ //求后繼 int t = ch[x][1]; while(ch[t][0]) t = ch[t][0]; return t; } int find(int v){ //查找v在SPT中的位置 int x = root; while(x && val[x] != v) x = ch[x][val[x] < v]; return x; } void del(int v){//刪除一個數(shù)v int x = find(v); if(!x) return; splay(x, 0); //把待刪除節(jié)點旋轉(zhuǎn)到根 if(!ch[root][0] || !ch[root][1]){ root = ch[root][0] + ch[root][1], fa[root] = 0; }else{//若根有兩個兒子，把根的后繼旋轉(zhuǎn)到根的右兒子，再提到根 int t = getsub(root); splay(t, root); ch[ch[root][1]][0] = ch[root][0], root = ch[root][1]; fa[ch[root][0]] = root, fa[root] = 0; pushup(root); } } bool insert(int v){ //插入一個數(shù)v if(!root) newnode(root, 0, v); else{ int x = root; while(ch[x][val[x] < v]){ if(val[x] == v){ splay(x, 0); return false; } x = ch[x][val[x] < v]; } newnode(ch[x][val[x] < v], x, v); splay(ch[x][val[x] < v], 0); } return true; }}using namespace SplayTree;int n, a, b, type;int main(){ root = ans = tot = 0; insert(-inf); insert(inf); scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d%d", &a, &b); if(siz[root] == 2){ type = a; } if(type == a) insert(b); else{ insert(b); int c = val[getpre(root)], d = val[getsub(root)]; c = b - c <= d - b ? c : d; ans = (ans % mod + abs(b - c) % mod) % mod; del(b); del(c); } } printf("%d/n", ans); return 0;}解題方法2，用set或者平衡樹，思路一樣
#include <bits/stdc++.h>using namespace std;const int inf = 0x7fffffff;const int mod = 1000000;set <int> s;int n, t, ans;void solve(int x){ set <int> :: iterator l = --s.lower_bound(x), r = s.lower_bound(x); if(x - *l <= *r - x && *l != -inf){ ans += x - *l; s.erase(l); } else{ ans += *r - x; s.erase(r); } ans %= mod;}int main(){ s.insert(inf); s.insert(-inf); scanf("%d", &n); for(int i = 1; i <= n; i++){ int a, b; scanf("%d%d", &a, &b); if(s.size() == 2){ t = a; s.insert(b); } else if(a == t) s.insert(b); else solve(b); } printf("%d/n", ans);}新聞熱點
疑難解答
