POJ 3617 Best Cow Line（最佳奶牛隊伍）

POJ 3617 Best Cow Line

Time Limit:?1000MS　　Memory Limit:?65536K

【Description】

【題目描述】

FJ is about to take his N (1 ≤ N ≤ 2,000) cows to the annual "Farmer of the Year" competition. In this contest every farmer arranges his cows in a line and herds them past the judges.

The contest organizers adopted a new registration scheme this year: simply register the initial letter of every cow in the order they will appear (i.e., If FJ takes Bessie, Sylvia, and Dora in that order he just registers BSD). After the registration phase ends, every group is judged in increasing lexicographic order according to the string of the initials of the cows' names.

FJ is very busy this year and has to hurry back to his farm, so he wants to be judged as early as possible. He decides to rearrange his cows, who have already lined up, before registering them.

FJ marks a location for a new line of the competing cows. He then proceeds to marshal the cows from the old line to the new one by repeatedly sending either the first or last cow in the (remainder of the) original line to the end of the new line. When he's finished, FJ takes his cows for registration in this new order.

Given the initial order of his cows, determine the least lexicographic string of initials he can make this way.

FJ打算帶他的N（1 ≤ N ≤ 2,000）頭奶牛去參加"Farmer of the Year"比賽。在這個比賽中每個農夫都會把他們的奶牛排成一隊，然后經過評審團。

比賽方今年采用了一種新的登記方案：每頭牛的出場都以名字首字母進行簡要登記（換句話說，如果FJ帶了Bessie、Sylvia和Dora參加，那么他只要登記成BSD）。登記結束后，每組評判根據奶牛名字首字母串字典序升序評判。

FJ今年事特多又得趕回農場，想早點完事。因此他決定在登記前把已經排好隊的奶牛重排一遍。

FJ找了塊地給比賽的奶牛排新隊伍。接著他不斷把第一頭或最后一頭牛從舊（或者剩下的）隊伍轉移到新隊伍的尾部。搞定后，FJ會用這個新隊伍登記。

給你這群奶牛的大寫字母，找出上述方法排列后字典序最小的字符串。

【Input】

【輸入】

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains a single initial ('A'..'Z') of the cow in the ith position in the original line

* 第1行: 一個整數: N

* 第2..N+1行: 第i+1行包含表示第i個奶牛初始位置的一個大寫字母('A'..'Z')

【Output】	【輸出】
The least lexicographic string he can make. Every line (except perhaps the last one) contains the initials of 80 cows ('A'..'Z') in the new line.	輸出所能構造的最小字典序字符串。每行（最后一行不用管）包含80頭奶牛的大寫字母('A'..'Z')。

【Sample Input - 輸入樣例】

【Sample Output - 輸出樣例】

ABCBCD

【題解】

貪心法，取字典序最小的元素。

輸出時每次從舊隊伍的頭/尾取出較小的元素，如果字典序相同，就看看哪一邊能更快地輸出字典序較小的元素。

【代碼 C++】

 1 #include<cstdio>
 2 char data[2005];
 3 int i;
 4 bool cmp(int L, int R){
 5     if (data[L] == data[R]){
 6         while (data[L] == data[R] && L < R) ++L, --R;
 7     }
 8     return data[L] < data[R];
 9 }
10 void opt(char now){
11     if (i == 80) i = 0, puts("");
12     putchar(now), ++i;
13 }
14 int main(){
15     int L, R, n;
16     scanf("%d", &n);
17     for (i = 0; i < n; ++i) getchar(), data[i] = getchar();
18     for (i = L = 0, R = n - 1; L <= R;){
19         if (cmp(L, R)) opt(data[L++]);
20         else opt(data[R--]);
21     }
22     return 0;
23 }

轉載于:https://www.cnblogs.com/Simon-X/p/5309380.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/257499.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/257499.shtml
英文地址，請注明出處：http://en.pswp.cn/news/257499.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！