queue/prioity_queue

queue/prioity_queue

uva,144

1-25个学生，每人每年领40美元。一个防盗的atm机按照1.2...k的方式依次吐出硬币。

例如：第一次吐出1coin，第二次吐出2 coins 直到限制k。然后循环从1开始吐。学生插卡取钱，当达到限额就离开队列。

注意：只有当output store没钱了，才会向里面吐钱。所以每次学生最大领的钱数为k。没领到40继续排在末尾。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 using namespace std;
 5 
 6 struct Student
 7 {
 8     int id,need;
 9 };
10 
11 queue<Student> mp;
12 
13 int main()
14 {
15     int N,k;
16     while(scanf("%d %d",&N,&k) && N+k)
17     {
18         int i;
19         for(i=1;i<=N;i++)
20             mp.push((Student){i,40});
21         while(!mp.empty())
22         {
23             for(i=1;i<=k;i++)
24             {
25                 int remain=i;
26                 while(remain && !mp.empty())
27                 {
28                     Student now=mp.front();
29                     mp.pop();
30                     if(now.need > remain)
31                     {
32                         now.need-=remain;
33                         remain=0;
34                         mp.push(now);
35                     }
36                     else
37                     {
38                         remain-=now.need;
39                         printf("%3d",now.id);
40                     }
41                 }
42             }
43         }
44         puts("");
45     }
46     return 0;
47 }
View Code

uva,170

从上到下为栈思维。从左到右代表顺序是逆序的。即第一列为第13pile也就是中间片。

所以程序的输入如下。

有几个想法：输入可以直接输入一个字符串，用ch==' '使单词数加1，但是gets或scanf()非法。。。

用queue实现的话。注意pile的顺序。与栈正好相反。但是我实现了，输出时对的，但是老是wa。所以就没写了。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stack>
 4 
 5 using namespace std;
 6 
 7 typedef struct _qnode{
 8   int value;
 9   char color;
10   _qnode(int v,char c){value=v;color=c;}
11   _qnode(){}
12 }qnode;
13 
14 qnode retain[54];
15 
16 int value(char ch)
17 {
18   if(ch>='2' && ch<='9')
19     return ch-'1';
20   if(ch=='A') return 0;
21   if(ch=='T') return 9;
22   if(ch=='J') return 10;
23   if(ch=='Q') return 11;
24   if(ch=='K') return 12;
25 }
26 
27 char Maps[]="A23456789TJQK";
28 
29 stack<qnode> mp[13];
30 int main()
31 {
32   char V,C;
33   while(cin>>V && V!='#')
34   {
35     cin>>C;
36     retain[0]=qnode(value(V),C);
37     for(int i=1;i<52;i++)
38     {
39       cin>>V>>C;
40       retain[i]=qnode(value(V),C);
41     }
42 
43     for(int i=51;i>=0;i--)
44       mp[12-i%13].push(retain[i]);
45     int count=0,index=12;
46     qnode now;
47     while(!mp[index].empty())
48     {
49       now=mp[index].top();
50       mp[index].pop();
51       index=now.value;
52       ++count;
53     }
54     if(count<10) cout<<"0";
55     cout<<count<<","<<Maps[now.value]<<now.color<<endl;
56   }
57   return 0;
58 }
View Code

花了一下午时间用queue实现了。原来是queue要放在main函数里面要不然每次值都被保存下来了。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <queue>
 4 
 5 using namespace std;
 6 
 7 typedef struct _qnode{
 8   int value;
 9   char color;
10   _qnode(int v,char c){value=v;color=c;}
11   _qnode(){}
12 }qnode;
13 
14 qnode retain[54];
15 
16 int value(char ch)
17 {
18   if(ch>='2' && ch<='9')
19     return ch-'1';
20   if(ch=='A') return 0;
21   if(ch=='T') return 9;
22   if(ch=='J') return 10;
23   if(ch=='Q') return 11;
24   if(ch=='K') return 12;
25 }
26 
27 char Maps[]="A23456789TJQK";
28 
29 int main()
30 {
31   char V,C;
32   while(cin>>V && V!='#')
33   {
34     queue<qnode> mp[13];
35     cin>>C;
36     retain[0]=qnode(value(V),C);
37     for(int i=1;i<52;i++)
38     {
39       cin>>V>>C;
40       retain[i]=qnode(value(V),C);
41     }
42 
43     for(int i=0;i<=51;i++)
44       mp[12-i%13].push(retain[i]);
45     int count=0,index=12;
46     qnode now;
47     while(!mp[index].empty())
48     {
49       now=mp[index].front();
50       mp[index].pop();
51       index=now.value;
52       count++;
53     }
54     if(count<10) cout<<"0";
55     cout<<count<<","<<Maps[now.value]<<now.color<<endl;
56   }
57   return 0;
58 }
View Code

uva,10142

  1 #include <algorithm>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <iostream>
  6 
  7 using namespace std;
  8 
  9 char candidate[21][81];
 10 char buf[1001];
 11 int choice[1001][21];
 12 int vote[21][1001];
 13 int vote_size[21];
 14 
 15 int main()
 16 {
 17     int t,n;
 18     while(~scanf("%d",&t))
 19     while(t--)
 20         {
 21             scanf("%d",&n);
 22             getchar();
 23             
 24             int i,j;
 25             
 26             for(i=0;i<n;++i)
 27             {
 28                 gets(candidate[i]);
 29                 vote_size[i]=0;
 30             }
 31             
 32             int number=0;
 33             while(gets(buf) && buf[0])
 34             {
 35                 int count=0,value=0;
 36                 
 37                 for(i=0;buf[i];++i)
 38                 {
 39                     if(buf[i]>='0' && buf[i]<='9')
 40                     {
 41                         value*=10;
 42                         value+=buf[i]-'0';
 43                     }
 44                     else
 45                     {
 46                         choice[number][count++]=value-1;
 47                         value=0;
 48                     }
 49                 }
 50                 choice[number++][count++]=value-1;
 51             }
 52             
 53             for(i=0;i<number;++i)
 54             {
 55                 int can=choice[i][0];
 56                 vote[can][vote_size[can]++]=i;
 57             }
 58             
 59             while(1)
 60             {
 61                 int max=0,min=1001,max_space,min_space;
 62                 for(i=0;i<n;i++)
 63                 {
 64                     if(vote_size[i]){   //不加的话，多扫多次会tle
 65                     if(max<vote_size[i])
 66                     {
 67                         max=vote_size[i];
 68                         max_space=i;
 69                     }
 70                     if(min>vote_size[i])
 71                     {
 72                         min=vote_size[i];
 73                         min_space=i;
 74                     }
 75                     }
 76                 }
 77                 
 78                 if(2*max>=number) break;
 79                 if(max==min) break;
 80                 
 81                 for(int k=0;k<n;++k)
 82                 {
 83                     if(vote_size[k]!=min) continue;
 84                     
 85                     for(i=0;i<vote_size[k];++i)
 86                     {
 87                         int per=vote[k][i];
 88                         
 89                         for(j=0;j<n;j++)
 90                         {
 91                             int can=choice[per][j];
 92                             
 93                             if(vote_size[can]!=min && vote_size[can])
 94                             {
 95                                 vote[can][vote_size[can]++]=per;
 96                                 break;
 97                             }
 98                         }
 99                     }
100                     vote_size[k]=0;
101                 }
102             }
103             
104             int max_space=0;
105             
106             for(i=0;i<n;++i)
107                 if(vote_size[max_space]<vote_size[i])
108                     max_space=i;
109             for(i=0;i<n;++i)
110                 if(vote_size[i]==vote_size[max_space])
111                     puts(candidate[i]);
112             
113             if(t) puts("");
114         }
115     return 0;
116 }
View Code

Poj,2051

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <queue>
 5 
 6 using namespace std;
 7 
 8 struct Register
 9 {
10     int id;
11     int period;
12     Register(int _id,int _period)
13     {
14         id=_id;
15         period=_period;
16     }
17     bool operator< (const Register& x)const
18     {
19         if(x.period==period)
20             return id>x.id;
21         return period>x.period;
22     }
23 };
24 
25 priority_queue<Register> mp;
26 char ch[20];
27 int np[3001]={0};
28 
29 int main()
30 {
31     int ID,PERIOD;
32     while(~scanf("%s",ch))
33     {
34         if(ch[0]=='#')
35             break;
36         scanf("%d %d",&ID,&PERIOD);
37         np[ID]=PERIOD;
38         mp.push(Register(ID,PERIOD));
39     }
40     
41     int k;
42     scanf("%d",&k);
43     for(int i=0;i<k;i++)
44     {
45         Register now=mp.top();
46         mp.pop();
47         printf("%d
",now.id);  //中间这里犯糊涂了，其实就是寡的优先队列
48         now.period+=np[now.id];
49         mp.push(now);
50     }
51     return 0;
52 }
View Code

 Poj,2062

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cmath>
 6 
 7 using namespace std;
 8 
 9 struct Node{
10     int value;
11     int suit;
12 }P1[30],P2[30];
13 
14 bool cmp(const Node& x,const Node& y)
15 {
16     if(x.value==y.value) return x.suit<y.suit;
17     return x.value<y.value;
18 }
19 
20 int value1(char ch)
21 {
22     if(ch>='0' && ch<='9')
23         return ch-'0';
24     if(ch=='T') return 10;
25     if(ch=='J') return 11;
26     if(ch=='Q') return 12;
27     if(ch=='K') return 13;
28     if(ch=='A') return 15;
29 }
30 
31 int value2(char ch)
32 {
33     if(ch=='C') return 1;
34     if(ch=='D') return 2;
35     if(ch=='S') return 3;
36     if(ch=='H') return 4;
37 }
38 
39 int main()
40 {
41     int n,k;
42     scanf("%d",&n);
43     while(n--)
44     {
45         int i;
46         char v,s;
47         scanf("%d",&k);
48         
49         for(i=0;i<k;i++)
50         {
51             cin>>v>>s;
52             P1[i]=(Node){value1(v),value2(s)};
53         }
54         sort(P1,P1+k,cmp);
55         
56         for(i=0;i<k;i++)
57         {
58             cin>>v>>s;
59             P2[i]=(Node){value1(v),value2(s)};
60         }
61         sort(P2,P2+k,cmp);
62         
63         int cnt=0,j=0;
64         int ans=0;  //ans纪录已经到达的位置，下次就从其下一次开始。
65         for(i=0;i<k;i++)
66         {
67             for(j=ans;j<k;j++)
68             {
69                 if(P2[j].value==P1[i].value)
70                 {
71                     if(P2[j].suit>P1[i].suit)
72                     {
73                         ans=j+1;
74                         cnt++;
75                         break;
76                     }
77                 }
78                 else if(P2[j].value>P1[i].value)
79                 {
80                     ans=j+1;
81                     cnt++;
82                     break;
83                 }
84             }
85         }
86         printf("%d
",cnt);
87     }
88     return 0;
89 }
View Code
活在现实，做在梦里。
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/do-it-best/p/5372209.html