[HOJ] 317 - 體重問題

Problem : 317 - 體重問題

Special Judge

Problem：

每個人都有不為人知的秘密，例如體重。

每當學期初大家都要量體重，但誰也不會輕易透漏自己的體重，萬一不小心成為最重的人，可能會被全班嘲笑一學期，這是誰也無法忍受的。

保健室阿姨是非常邪惡的，公布了所有相鄰的兩座號誰的體重較重的資訊，並且公告了m 個可能的體重值，代表班上所有人的體重必定是這m 個數字其中之一。

邪惡如保健室阿姨的小明想要偷偷找出每個人的體重可能多重，你能幫助他嗎？

Input：

第一行有兩個正整數n;m。表示一共有n 個人，可能的體重值有m 種。

第二行有m 個以空白隔開的正整數，依序表示這m 種可能的體重值Wi。

接著是一個長度為n-1 且由'L', 'R', '=' 所構成的字串，若第i 個字元為'L'，表示座號i的體重大於座號i+1的體重；若第i個字元為'R'，表示座號i的體重小於座號i+1的體重；若第i個字元為'='，表示座號i與座號i+1的體重相等。

限制：
保證有10% 的測試資料滿足:
1 ≤ n,m ≤ 8
保證有30% 的測試資料滿足:
1 ≤ n,m ≤ 10³
保證所有的測試資料滿足:
1 ≤ n,m ≤ 10⁵
1 ≤ Wi ≤ 10⁹

W1, W2 ... Wm 皆為相異數字。

Output：

若存在一組解，輸出n行，第i行有一個正整數表示座號i的人的體重，若存在多組解，請輸出任意一組解即可。

若不存在任何一組解請輸出"No"(不包含雙引號)。

Sample Input：

Sample #1:
3 5
1 2 3 4 5
RR

Sample #2:
5 2
1 2
LRLR

Sample #3:
5 2
1 2
LLRR

Sample Output：

Sample #1:
2
3
4

Sample #2:
2
1
2
1
2

Sample #3:
No

-----------------------------------------------------------------------------------------------------------

#include<stdio.h>

#include<algorithm>

using namespace std;

int s[100005],d[100005];

char c[100005];

int main(){

    int minn=1,maxx=1,n,m,i,p=1;

    scanf("%d%d",&n,&m);

    for(i=0;i<m;i++)

        scanf("%d",&s[i]);

    sort(s,s+m);

    d[0]=1;

    scanf("%s",c);

    for(i=0;i<n-1;i++){

        if(c[i]=='R') p++;

        else if(c[i]=='L') p--;

        minn=min(minn,p);

        maxx=max(maxx,p);

        d[i+1]=p;

    }

    if(maxx-minn+1>m) puts("No");

    else{

        for(i=0;i<n;i++){

            printf("%d\n",s[d[i]+minn*-1]);

        }

    }

}