POJ 1010

时间：2010-08-17 来源：Ray Z

code   1 #include <iostream>
  2 using namespace std;
  3
  4 int stamps[500];
  5 int s[4];
  6 int n; //number of stamp types
  7 int m; //number of customer request
  8 int k; //number of stamps sold
  9 int t; //types of stamps sold
10 int maxValue; //highest single stamp value
11 int curK; //numbers of stamps sold of current best solution
12 int curT; //types of stamps sold of current best solution
13 int curM; //highest single stamp value of current best solution
14 int curS[4]; //current best solution
15 bool curTie; //if there is a tie
16
17 bool LessThan5(int value)
18 {
19     int count = 0;
20     for(int i=0; i<n; i++)
21     {
22         if(stamps[i] == value)
23         {
24             count++;
25         }
26     }
27     return count < 5;
28 }
29
30 void Test()
31 {
32     for(s[0]=0; s[0]<n; s[0]++)
33     {
34         for(s[1]=s[0]; s[1]<n; s[1]++)
35         {
36             for(s[2]=s[1]; s[2]<n; s[2]++)
37             {
38                 for(s[3]=s[2]; s[3]<n; s[3]++)
39                 {
40                     if(stamps[s[0]]+stamps[s[1]]+stamps[s[2]]+stamps[s[3]] != m)
41                     {
42                         continue;
43                     }
44
45                     k = 0;
46                     t = 0;
47                     maxValue = 0;
48                     if(stamps[s[0]])
49                     {
50                         k++;
51                         t++;
52                         if(stamps[s[0]] > maxValue)
53                         {
54                             maxValue = stamps[s[0]];
55                         }
56                     }
57
58                     if(stamps[s[1]])
59                     {
60                         k++;
61                         if(s[1] > s[0])
62                         {
63                             t++;
64                         }
65                         if(stamps[s[1]] > maxValue)
66                         {
67                             maxValue = stamps[s[1]];
68                         }
69                     }
70
71                     if(stamps[s[2]])
72                     {
73                         k++;
74                         if(s[2] > s[1])
75                         {
76                             t++;
77                         }
78                         if(stamps[s[2]] > maxValue)
79                         {
80                             maxValue = stamps[s[2]];
81                         }
82                     }
83
84                     if(stamps[s[3]])
85                     {
86                         k++;
87                         if(s[3] > s[2])
88                         {
89                             t++;
90                         }
91                         if(stamps[s[3]] > maxValue)
92                         {
93                             maxValue = stamps[s[3]];
94                         }
95                     }
96
97                     if(t < curT)
98                     {
99                         continue;
100                     }
101
102                     if(t > curT)
103                     {
104                         curT = t;
105                         curK = k;
106                         curM = maxValue;
107                         curS[0] = s[0];
108                         curS[1] = s[1];
109                         curS[2] = s[2];
110                         curS[3] = s[3];
111                         curTie = false;
112                         continue;
113                     }
114
115                     if(k > curK)
116                     {
117                         continue;
118                     }
119
120                     if(k < curK)
121                     {
122                         curT = t;
123                         curK = k;
124                         curM = maxValue;
125                         curS[0] = s[0];
126                         curS[1] = s[1];
127                         curS[2] = s[2];
128                         curS[3] = s[3];
129                         curTie = false;
130                         continue;
131                     }
132
133                     if(maxValue < curM)
134                     {
135                         continue;
136                     }
137
138                     if(maxValue > curM)
139                     {
140                         curT = t;
141                         curK = k;
142                         curM = maxValue;
143                         curS[0] = s[0];
144                         curS[1] = s[1];
145                         curS[2] = s[2];
146                         curS[3] = s[3];
147                         curTie = false;
148                         continue;
149                     }
150
151                     curTie = true;
152                 }
153             }
154         }
155     }
156
157     if(curT == -1)
158     {
159         cout << m << " ---- none" << endl;
160         return;
161     }
162
163     cout << m << " (" << curT << "):";
164     if(curTie)
165     {
166         cout << " tie" << endl;
167         return;
168     }
169
170     for (int i=0; i<4; i++)
171     {
172         if (stamps[curS[i]] > 0 )
173         {
174             cout << ' '<< stamps[curS[i]];
175         }
176     }
177
178     cout<<endl;
179 }
180
181 int main()
182 {
183     int tag;
184     while(cin >> tag)
185     {
186         //very important: to make stamps[0] = 0
187         n = 1;
188         stamps[n++] = tag;
189         while(cin >> tag && tag)
190         {
191             if(LessThan5(tag))
192             {
193                 stamps[n++] = tag;
194             }
195         }
196
197         while(cin >> m && m)
198         {
199             curK = -1;
200             curT = -1;
201             curM = -1;
202             curTie = false;
203             Test();
204         }
205     }
206
207     return 0;
208 }