2016年1月14日 星期四

[HOJ 281]Balls

HOJ生病惹QQ,因此我在這裡做了題目備份,請參考~

我們可以構造出一個策略:
1. 如果可以消掉任何一種顏色,就把它消掉
2. 如果管子是空的,或者只有一顆消不掉的球,就隨便選個方向塞進去
3. 如果只剩一顆球,隨便選個方向塞進去就結束了
4. 如果接下來連續兩顆球顏色相同,就隨便選個方向把兩顆都塞進去消掉
5. 如果接下來連續兩顆球顏色不同,因為這時管子兩邊的球顏色一定不會相同,所以第二顆球一定可以消掉左右其中一顆球,這時將第一顆球塞進另一個方向,第二顆球去玩消消樂
6. 不會有第六種情況惹
最後管子中剩的球一定顏色都不相同(每種顏色最多一顆)
很明顯,這一定是最佳解

code:
#include<cstdio>
#include<cassert>
#include<deque>
using namespace std;
int N;
char S[200001];
deque<char>TUBE;
void PutLeft(const char c)
{
    putchar('L');
    if(!TUBE.empty()&&TUBE.front()==c)TUBE.pop_front();
    else TUBE.push_front(c);
}
void PutRight(const char c)
{
    putchar('R');
    if(!TUBE.empty()&&TUBE.back()==c)TUBE.pop_back();
    else TUBE.push_back(c);
}
int main()
{
    scanf("%d%s",&N,S);
    for(int i=0;i<N;i++)
    {
        if(TUBE.empty())PutLeft(S[i]);
        else if(TUBE.front()==S[i])PutLeft(S[i]);
        else if(TUBE.back()==S[i])PutRight(S[i]);
        else if(i==N-1||(int)TUBE.size()==1)PutLeft(S[i]);
        else if(S[i]==S[i+1])PutLeft(S[i]),PutLeft(S[++i]);
        else if(S[i+1]==TUBE.front())PutRight(S[i]),PutLeft(S[++i]);
        else if(S[i+1]==TUBE.back())PutLeft(S[i]),PutRight(S[++i]);
        else assert(0);
    }
    puts("");
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原