VIJOS P1647 不差钱 SBT

【描述】

同学们一起看了小品《不差钱》，LX神突发奇想，想刁难一下十八居士，他让十八居士模拟一下点菜的过程。

【输入格式】

输入第一行为一个数price，表示价钱大于price的菜赵本山都不要。

以下几行表示点菜的过程，每行两个整数p，n

p=1 表示在菜谱中添加一个价格为n的菜,这是第i个1号命令，这个菜的编号就是i，

p=2 表示菜谱中第n号菜已卖完（但不代表菜谱中没有了这种菜），

p=3 表示赵本山点第n贵的菜。

输入文件以0结束。

菜的价格0<n<=10^6。

3种命令， 30%数据命令最多300次， 60%数据命令最多3000次， 100%数据命令最多100000次。

【输出格式】

对于每个p=3，如果第n贵的菜价格高于price，则输出“Dui bu qi,Mei you.”。

如果第n贵的菜价格不高于price，且没有卖完，则输出“You.”然后输出价格" m Yuan."；

如果已卖完，则输出“Mei you. Zhe ge ke yi you. Zhe ge zhen mei you!”

【分析】

题目意思表达得比较明确，本题也很适合作为SBT的模板题。

菜的编号就是存在SBT静态数组中的下标，只要加一个是否empty的标记即可。

唯一稍微可能有点问题的是出现多个相同菜价的菜时的选择问题，一开始按照普通二叉树的写法写SBT的前趋后继，后来发现这样做其实是不严谨的，因为左右旋操作的存在，虽然一开始相等的数是插入到右边去，但是不能保证不会因为左旋而把父节点旋到左子树去了，所以最后只能保证左子树的值不大于根，右子树的值不小于根，相等值是完全没办法判断的。

......最后只好继续查找第n-1大、n-2大...第n+1大、第n+2大...直到找到不相等为止，O（k*logn）遍历一遍相等的数。

好在测试时间上好像还不错，不知道又没有更好的办法？

 /* ***********************************************

 MYID    : Chen Fan

 LANG    : G++

 PROG    : VIJOS1647

 ************************************************ */

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 #define MAXN 100010

 typedef struct sbtnod

 {

     int key,left,right,size;

     bool empty;

 } sbtnode;

 int sbttail,sbt;

 sbtnode tree[MAXN];

 void rrotate(int& t)

 {

     int k=tree[t].left;

     if (!k) return ;

     tree[t].left=tree[k].right;

     tree[k].right=t;

     tree[k].size=tree[t].size;

     tree[t].size=tree[tree[t].left].size+tree[tree[t].right].size+;

     t=k;

 }

 void lrotate(int& t)

 {

     int k=tree[t].right;

     if (!k) return ;

     tree[t].right=tree[k].left;

     tree[k].left=t;

     tree[k].size=tree[t].size;

     tree[t].size=tree[tree[t].left].size+tree[tree[t].right].size+;

     t=k;

 }

 void maintain(int& t,bool flag)

 {

     if (!t) return ;

     if (!flag)

         if (tree[tree[tree[t].left].left].size>tree[tree[t].right].size) rrotate(t);

         else if (tree[tree[tree[t].left].right].size>tree[tree[t].right].size)

         {

             lrotate(tree[t].left);

             rrotate(t);

         } else return ;

     else

         if (tree[tree[tree[t].right].right].size>tree[tree[t].left].size) lrotate(t);

         else if (tree[tree[tree[t].right].left].size>tree[tree[t].left].size)

         {

             rrotate(tree[t].right);

             lrotate(t);

         } else return ;

     maintain(tree[t].left,false);

     maintain(tree[t].right,true);

     maintain(t,false);

     maintain(t,true);

 }

 void insert(int& t,int v)

 {

     if (!t)

     {

         sbttail++;

         tree[sbttail].key=v;

         tree[sbttail].size=;

         tree[sbttail].empty=false;

         t=sbttail;

     } else

     {

         tree[t].size++;

         if (v<tree[t].key) insert(tree[t].left,v);

         else insert(tree[t].right,v);

         maintain(t,v>=tree[t].key);

     }

 }

 int select(int t,int k)

 {

     if (k==tree[tree[t].left].size+) return t;

     if (k<=tree[tree[t].left].size) return select(tree[t].left,k);

     else return select(tree[t].right,k--tree[tree[t].left].size);

 }

 int main()

 {

     freopen("1.txt","r",stdin);

     int pri;

     scanf("%d",&pri);

     sbt=;

     sbttail=;

     int p,n;

     while(scanf("%d%d",&p,&n)==)

     {

         switch(p)

         {

             case :

                 insert(sbt,n);

                 break;

             case :

                 tree[n].empty=true;

                 break;

             case :

                 n=sbttail-n+;

                 int temp=select(sbt,n);

                 if (tree[temp].key>pri) printf("Dui bu qi,Mei you.\n");

                 else

                 {

                     bool done=false;

                     if (!tree[temp].empty)

                     {

                         done=true;

                         printf("You. %d Yuan.\n",tree[temp].key);

                     } else

                     {

                         int pre,p=n;

                         while(p>&&(!done))

                         {

                             p--;

                             pre=select(sbt,p);

                             if (tree[pre].key<tree[temp].key) break;

                             if (!tree[pre].empty)

                             {

                                 done=true;

                                 printf("You. %d Yuan.\n",tree[temp].key);

                             }

                         }

                         int suc,s=n;

                         while(s<n&&(!done))

                         {

                             s++;

                             suc=select(sbt,s);

                             if (tree[suc].key>tree[temp].key) break;

                             if (!tree[suc].empty)

                             {

                                 done=true;

                                 printf("You. %d Yuan.\n",tree[temp].key);

                             }

                         }

                     }

                     if (!done) printf("Mei you. Zhe ge ke yi you. Zhe ge zhen mei you!\n");

                 }

         }

     }

     return ;

 }

巴特西

VIJOS P1647 不差钱 SBT

【描述】

【输入格式】

【输出格式】

最新文章

热门文章