[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;
}