BZOJ 1640/1692 : [Usaco2007 Nov]Best Cow Line 队列变换 (贪心)
1640: [Usaco2007 Nov]Best Cow Line 队列变换
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 710 Solved: 373 [Submit][Status][Discuss]
Description
FJ打算带着他可爱的N (1 ≤ N ≤ 2,000)头奶牛去参加”年度最佳老农”的比赛.在比赛中,每个农夫把他的奶牛排成一列,然后准备经过评委检验. 比赛中简单地将奶牛的名字缩写为其头字母(the initial letter of every cow),举个例子,FJ带了Bessie, Sylvia,和Dora,那么就可以缩写为BSD. FJ只需将奶牛的一个序列重新排列,然后参加比赛.他可以让序列中的第一头奶牛,或者最后一头走出来,站到新队列的队尾. 利欲熏心的FJ为了取得冠军,他就必须使新队列的字典序尽量小. 给你初始奶牛序列(用头字母)表示,然后按照上述的规则组成新序列,并使新序列的字典序尽量小.
Input
第1行:一个整数N.
第2行至第N+1行:每行一个大写字母,表示初始序列中该奶牛的头字母.
Output
得到的最小字典序的序列.每输出80个字母需要一个换行!
Sample Input
6 A C D B C B
Sample Output
ABCBCD
HINT
Source
思路：比较麻烦的一个贪心。。对拍才找出了一个错误。。。
写丑了QAQ
1/* ***********************************************
2Author :111qqz
3Created Time :2016年04月08日 星期五 16时16分34秒
4File Name :code/bzoj/1640.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=2E3+7;
34int n;
35int a[N];
36string ans;
37int main()
38{
39 #ifndef ONLINE_JUDGE
40 freopen("code/in.txt","r",stdin);
41 #endif
42
43 ios::sync_with_stdio(false);
44 cin>>n;
45 ans ="";
46 for ( int i = 1 ;i <= n ; i++)
47 {
48 char ch;
49 cin>>ch;
50 a[i] = ch-'A'+1;
51 }
52
53 int l = 1;
54 int r = n ;
55
56 while (l<=r)
57 {
58 if (l==r)
59 {
60 // cout<<"aans:"<<ans<<endl;
61 ans += char(a[l]+64);
62 // cout<<"aaans:"<<ans<<endl;
63
64 break;
65 }
66 if (a[l]!=a[r])
67 {
68 if (a[l]<a[r])
69 {
70 ans += char(a[l]+64);
71 l++;
72 }
73 else
74 {
75 ans += char(a[r]+64);
76 r--;
77 }
78 }
79 else
80 {
81 if (l==r) continue;
82 int tmpl = l;
83 int tmpr = r;
84 while (a[tmpl]==a[tmpr]&&tmpl<tmpr)
85 {
86 tmpl++;
87 tmpr--;
88 }
89// cout<<"tmpl:"<<tmpl<<" tmpr:"<<tmpr<<" ans:"<<ans<<endl;
90 if (tmpl>=tmpr)
91 {
92 while (l<=r)
93 {
94 // cout<<"l:"<<l<<" r:"<<r<<" ans:"<<ans<<endl;
95
96
97 if (a[l]<=a[r])
98 {
99 ans += char(a[l]+64);
100 l++;
101 break;
102 }
103 else
104 {
105 ans += char(a[r]+64);
106 r--;
107 break;
108 }
109 //cout<<" ans:"<<ans<<endl;
110 }
111 /* for ( int i = l ; i <= r ; i++)
112 {
113 if (tmpl==tmpr&&a[tmpl]>a[l]&&i==tmpl) continue;
114 ans +=char(a[i]+64);
115 }
116 if (tmpl==tmpr&&a[tmpl]>a[l]) ans += char(a[tmpl]+64); */
117 //break;
118 }
119 else
120 {
121 while (l<tmpl&&r>tmpr)
122 {
123 // cout<<"l:"<<l<<" r:"<<r<<" anssss:"<<ans<<endl;
124
125 if (a[l]==a[r])
126 {
127 if (a[tmpl]<=a[tmpr])
128 {
129 ans += char(a[l]+64);
130 l++;
131 break;
132 }else
133 {
134 ans += char(a[r]+64);
135 r--;
136 break;
137 }
138
139 }
140 else
141 {
142
143 if (a[l]<a[r])
144 {
145 ans+=char(a[l]+64);
146 l++;
147 break;
148 }
149 else
150 {
151 ans+=char(a[r]+64);
152 r--;
153 break;
154 }
155 // cout<<"l:"<<l<<" r:"<<r<<" anssss:"<<ans<<endl;
156 }
157 }
158 /* if (a[tmpl]<a[tmpr])
159 {
160 for ( int i = l ; i <= tmpl ; i++) ans +=char(a[i]+64);
161 l = tmpl+1;
162 }
163 else
164 {
165 for ( int i = r ; i >= tmpr ; i--) ans +=char(a[i]+64);
166 r = tmpr-1;
167 } */
168 }
169 }
170 // cout<<"l:"<<l<<" r:"<<r<<" ans:"<<ans<<endl;
171
172 }
173 int len = ans.length();
174 for ( int i = 0 ; i < len ; i++)
175 {
176 cout<<ans[i];
177 if ((i+1)==0) cout<<endl;
178 }
179// cout<<ans<<endl;
180 #ifndef ONLINE_JUDGE
181 fclose(stdin);
182 #endif
183 return 0;
184}
185
186
187
188
189
190
191
192出错数据：
193input:
194393
195A
196C
197A
198A
199B
200C
201C
202C
203C
204B
205B
206C
207A
208C
209C
210C
211B
212B
213A
214C
215C
216B
217C
218C
219C
220C
221A
222A
223A
224A
225C
226A
227A
228A
229B
230C
231C
232C
233B
234A
235A
236B
237A
238A
239B
240C
241C
242C
243A
244A
245C
246A
247C
248A
249C
250B
251C
252C
253B
254A
255A
256B
257C
258B
259B
260A
261B
262B
263C
264A
265B
266A
267B
268B
269B
270B
271B
272B
273A
274B
275A
276B
277A
278C
279B
280A
281B
282B
283B
284A
285B
286C
287C
288A
289B
290B
291C
292C
293A
294B
295C
296C
297A
298C
299C
300B
301A
302A
303A
304A
305A
306A
307B
308A
309A
310A
311B
312C
313B
314C
315A
316A
317C
318A
319B
320A
321B
322A
323C
324C
325A
326C
327C
328A
329B
330C
331C
332B
333C
334C
335A
336A
337B
338C
339B
340B
341A
342A
343B
344B
345A
346B
347C
348C
349C
350C
351A
352C
353A
354A
355B
356A
357A
358B
359B
360B
361A
362A
363A
364B
365B
366B
367B
368C
369A
370A
371B
372B
373B
374A
375A
376B
377B
378A
379C
380C
381C
382C
383B
384A
385A
386A
387B
388A
389C
390B
391B
392A
393C
394C
395B
396A
397A
398B
399A
400C
401C
402C
403A
404A
405C
406B
407C
408C
409C
410B
411B
412C
413B
414C
415A
416B
417C
418A
419C
420C
421B
422A
423A
424A
425B
426C
427C
428C
429B
430C
431B
432A
433A
434C
435B
436C
437A
438C
439B
440A
441A
442C
443B
444B
445C
446B
447A
448A
449C
450C
451C
452A
453B
454A
455C
456A
457B
458B
459C
460C
461B
462C
463B
464B
465B
466A
467C
468C
469C
470A
471B
472A
473B
474C
475C
476B
477B
478A
479B
480B
481A
482C
483C
484C
485C
486B
487C
488A
489A
490A
491A
492A
493C
494C
495C
496B
497C
498B
499A
500C
501A
502B
503A
504C
505B
506C
507A
508A
509A
510A
511C
512C
513C
514B
515B
516B
517B
518C
519C
520B
521A
522A
523C
524C
525C
526A
527A
528C
529B
530B
531B
532C
533B
534C
535B
536C
537C
538A
539A
540C
541A
542C
543C
544C
545C
546B
547A
548A
549B
550A
551C
552B
553B
554C
555B
556B
557C
558B
559B
560B
561C
562A
563C
564B
565A
566B
567B
568C
569C
570B
571C
572C
573C
574A
575C
576B
577C
578B
579B
580A
581B
582B
583C
584B
585A
586A
587C
588
589我的输出：ACAABCBBABBCAABCBCACCCBCCBBABCACBBBCBBCBBCABAABCCCCACAACCBCBCBBBCAACCCAABCCBBBBC
590CCAAAACBCABACABCBCCCAAAAACBCCCCABBABBCCBABACCCABBBCBCCBBACABACCCAABCBBCAABCACBCA
591ABCBCCCBAAABCCACBACBCBBCCCBCAACCCABAABCCABBCABAAABCCCCABBAABBBAACBBBBAAABBBAABAA
592CACCCCBABBAABBCBAACCBCCBACCACCABABACAACBCBAAABAAAAAABCCACCBACCBBACCBABBBABCABABA
593BBBBBBABACBBABBCBAABCCBCACACAACCCBAABAABCCCBAAACAAAACCCCBBCACCCBBACCBCCCC
594
595正确输出：ACAABCAABCBBABBCBCACCCBCCBBABCACBBBCBBCBBCABAABCCCCACAACCBCBCBBBCAACCCAABCCBBBBC
596CCAAAACBCABACABCBCCCAAAAACBCCCCABBABBCCBABACCCABBBCBCCBBACABACCCAABCBBCAABCACBCA
597ABCBCCCBAAABCCACBACBCBBCCCBCAACCCABAABCCABBCABAAABCCCCABBAABBBAACBBBBAAABBBAABAA
598CACCCCBABBAABBCBAACCBCCBACCACCABABACAACBCBAAABAAAAAABCCACCBACCBBACCBABBBABCABABA
599BBBBBBABACBBABBCBAABCCBCACACAACCCBAABAABCCCBAAACAAAACCCCBBCACCCBBACCBCCCC