題意：
? ? ? 一條蛇生活在一個(gè)管子里，然后管子上面的某些位置會(huì)一次出現(xiàn)食物，每次蛇都會(huì)吃最近的食物，吃完之后就原地不動(dòng)，等待下一次吃食物，如果有兩個(gè)食物距離蛇一樣遠(yuǎn)并且都是最近的，那么蛇不會(huì)掉頭，而是直接按他最后停留的方向走，去吃自己前方的食物，最后給一些命令，問蛇一共走了多少路。

思路：

? ? ? 看完一下就想到了set,結(jié)果果斷用set過(guò)了，后來(lái)聽說(shuō)這個(gè)題目可以用線段樹來(lái)做，自己想了下，用線段樹也不是很難，結(jié)果又寫了個(gè)線段樹，也AC了，set用時(shí)359ms，線段樹用了515ms，無(wú)論是哪個(gè)方法，這個(gè)題目就是要迅速的找到比當(dāng)前值大的最小的那個(gè)數(shù)，和比當(dāng)前值小的最大的那個(gè)數(shù)（或者當(dāng)前值本身），如果是找大于等于的第一個(gè)數(shù)在set里可以直接 *my_set.lower_bound(now);,如果是小于等于也用同樣的方法，只不過(guò)是吧所有的數(shù)都存成負(fù)數(shù)就行了，對(duì)于線段樹也比較好寫，每個(gè)節(jié)點(diǎn)有兩個(gè)權(quán)值，一個(gè)是當(dāng)前區(qū)間的最大值，一個(gè)是最小值，然后就是簡(jiǎn)單的更新和查找了，要有一個(gè)就是這個(gè)題目同一個(gè)點(diǎn)可能同時(shí)存在多個(gè)食物，所以開個(gè)數(shù)組記錄每個(gè)節(jié)點(diǎn)的食物個(gè)數(shù)，吃了就--，如果是0就直接刪除就行了，具體的看代碼。

SET 359ms

#include<stdio.h> #include<set>#define INF 1000000000 using namespace std;set<int>low ,up; int num[110000];int abss(int x) {return x < 0 ? -x : x; }int main () {int t ,n ,m;int a ,b ,cas = 1;scanf("%d" ,&t);while(t--){scanf("%d %d" ,&n ,&m);low.clear() ,up.clear();memset(num ,0 ,sizeof(num));up.insert(INF);low.insert(INF);int now = 0;int sum = 0;int fx = 1;while(m--){scanf("%d" ,&a);if(!a){scanf("%d" ,&b);up.insert(b);low.insert(-b);num[b] ++;}else {a = *up.lower_bound(now);b = *low.lower_bound(-now);if(b != INF) b = -b;if(a == INF && b == INF) continue;if(!abss(a - now)) {if(!--num[a])up.erase(a) ,low.erase(-a);continue;}if(!abss(b - now)){if(!--num[b])up.erase(b) ,low.erase(-b);continue;} if(abss(a - now) < abss(b - now)){sum += abss(a - now);if(now < a) fx = 1;else fx = 2;now = a;if(!--num[a])up.erase(a) ,low.erase(-a);}else if(abss(a - now) > abss(b - now)){sum += abss(b - now);if(now < b) fx = 1;else fx = 2;now = b;if(!--num[b])up.erase(b) ,low.erase(-b);}else {sum += abss(a - now);if(fx == 1 && now < a || fx == 2 && now > a){now = a;if(!--num[a])up.erase(a) ,low.erase(-a);}else {now = b;if(!--num[b])up.erase(b) ,low.erase(-b);}}}}printf("Case %d: %d\n" ,cas ++ ,sum);}return 0; } 字典樹 515ms #include<stdio.h> #include<string.h>#define lson l ,mid ,t << 1 #define rson mid + 1 ,r ,t << 1 | 1 #define INF 100000000 int max[440000] ,min[440000]; int num[110000];int maxx(int x ,int y) {return x > y ? x : y; }int minn(int x ,int y) {return x < y ? x : y; }int abss(int x) {return x < 0 ? -x : x; }void Pushup(int t) {max[t] = maxx(max[t<<1] ,max[t<<1|1]);min[t] = minn(min[t<<1] ,min[t<<1|1]);return ; }void BuidTree(int n) {for(int i = 1 ;i <= n * 4 ;i ++)max[i] = -INF ,min[i] = INF;memset(num ,0 ,sizeof(num));return; }void Update(int l ,int r ,int t ,int a ,int b ,int c) {if(l == r){max[t] = b ,min[t] = c;return ;}int mid = (l + r) >> 1;if(a <= mid) Update(lson ,a ,b ,c);else Update(rson ,a ,b ,c);Pushup(t);return ; }int Query_max(int l ,int r ,int t ,int a ,int b) {if(a <= l && b >= r)return max[t];int mid = (l + r) >> 1;int ans = 0;if(a <= mid) ans = Query_max(lson ,a ,b);if(b > mid) ans = maxx(ans ,Query_max(rson ,a ,b));return ans; }int Query_min(int l ,int r ,int t ,int a ,int b) {if(a <= l && b >= r)return min[t];int mid = (l + r) >> 1;int ans = INF;if(a <= mid) ans = Query_min(lson ,a ,b);if(b > mid) ans = minn(ans ,Query_min(rson ,a ,b)); return ans; }int main () {int t ,m ,n ,i ,a ,b ,sum ,now ,fx ,cas = 1;scanf("%d" ,&t);while(t--){scanf("%d %d" ,&n ,&m);n++ ,now = 1 ,sum = 0 ,fx = 1;BuidTree(n);while(m--){scanf("%d" ,&a);if(!a){scanf("%d" ,&b);num[++b] ++;if(num[b] == 1) Update(1 ,n ,1 ,b ,b ,b);continue;}if(num[now]){sum += 0;if(!--num[now])Update(1 ,n ,1 ,now ,-INF ,INF);continue;}if(now == 1) a = -INF;else a = Query_max(1 ,n ,1 ,1 ,now - 1);if(now == n) b = INF;else b = Query_min(1 ,n ,1 ,now + 1 ,n);if(a == -INF && b == INF) continue;if(abss(a - now) < abss(b - now)){sum += abss(a - now);fx = a < now ? 1 : 2;now = a;if(!--num[now])Update(1 ,n ,1 ,now ,-INF ,INF);}else if(abss(a - now) > abss(b - now)){sum += abss(b - now);fx = b < now ? 1 : 2;now = b;if(!--num[now])Update(1 ,n ,1 ,now ,-INF ,INF);}else {sum += abss(a - now);if(fx == 1 && a < now || fx == 2 && a > now){now = a;if(!--num[now])Update(1 ,n ,1 ,now ,-INF ,INF); }else {now = b;if(!--num[now])Update(1 ,n ,1 ,now ,-INF ,INF);}}}printf("Case %d: %d\n" ,cas ++ ,sum);}return 0;}

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的hdu4302 set或者线段树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。