美團codeM資格賽 送外賣

送外賣

時間限制：1秒

空間限制：32768K

n 個小區排成一列，編号為從 0 到 n-1 。一開始，美團外賣員在第0号小區，目标為位于第 n-1 個小區的配送站。

給定兩個整數數列 a[0]~a[n-1] 和 b[0]~b[n-1] ，在每個小區 i 裡你有兩種選擇：

1) 選擇a：向前 a[i] 個小區。

2) 選擇b：向前 b[i] 個小區。

把每步的選擇寫成一個關于字元 ‘a’ 和 ‘b’ 的字元串。求到達小區n-1的方案中，字典序最小的字元串。如果做出某個選擇時，你跳出了這n個小區的範圍，則這個選擇不合法。 

• 當沒有合法的選擇序列時，輸出 “No solution!”。

• 當字典序最小的字元串無限長時，輸出 “Infinity!”。

• 否則，輸出這個選擇字元串。

字典序定義如下：串s和串t，如果串 s 字典序比串 t 小，則

• 存在整數 i ≥ -1，使得∀j，0 ≤ j ≤ i，滿足s[j] = t[j] 且 s[i+1] < t[i+1]。

• 其中，空字元 < ‘a’ < ‘b’。 

輸入描述:

輸入有 3 行。

第一行輸入一個整數 n (1 ≤ n ≤ 10^5)。

第二行輸入 n 個整數，分别表示 a[i] 。

第三行輸入 n 個整數，分别表示 b[i] 。

−n ≤ a[i], b[i] ≤ n      

輸出描述:

輸出一行字元串表示答案。      

輸入例子:

7
5 -3 6 5 -5 -1 6
-6 1 4 -2 0 -2 0      

輸出例子:

abbbb      

解題思路：先建構反向圖（本來是3能到6的，我加一條6到3的邊），從n出發，廣度優先搜尋（bfs）一遍，能到1就有解。同時記錄下哪些點被經過了，這在原圖中，就是能到n的點。然後從1出發，每個點貪心選擇：如果走a，這個點能到n，那就走a，否則走b。但如果走回到之前走過的點，那說明答案是Infinity。

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <climits>

using namespace std;

#define LL long long
const int INF = 0x3f3f3f3f;

vector<int> g[100005];
int a[100005],b[100005],n;
bool vis[100005];
bool vis1[100005];
char ch[100005];

void bfs()
{
    queue<int> q;
    vis[n]=1;
    q.push(n);
    while(!q.empty())
    {
        int pre=q.front();
        q.pop();
        int Size=g[pre].size();
        for(int i=0; i<Size; i++)
        {
            if(!vis[g[pre][i]])
            {
                vis[g[pre][i]]=1;
                q.push(g[pre][i]);
            }
        }
    }
}

int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++) g[i].clear();
        memset(vis,0,sizeof vis);
        memset(vis1,0,sizeof vis1);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            int k=i+a[i];
            if(k>=1&&k<=n) g[k].push_back(i);
        }
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&b[i]);
            int k=i+b[i];
            if(k>=1&&k<=n) g[k].push_back(i);
        }
        bfs();
        if(!vis[1]) {printf("No solution!\n");continue;}
        int p=0;
        vis1[1]=1;
        bool flag=0;
        for(int x=1; x!=n&&!flag;)
        {
            int xx=x+a[x];
            if(xx>=1&&xx<=n&&vis[xx])
            {
                if(!vis1[xx])
                {
                    vis1[xx]=1;
                    ch[p++]='a';
                }
                else flag=1;
                x=xx;
            }
            else
            {
                xx=x+b[x];
                if(xx>=1&&xx<=n&&vis[xx])
                {
                    if(!vis1[xx])
                    {
                        vis1[xx]=1;
                        ch[p++]='b';
                    }
                    else flag=1;
                }
                else
                {
                    flag=2;
                    break;
                }
                x=xx;
            }
        }
        ch[p]='\0';
        if(!flag) printf("%s\n",ch);
        else if(flag==1) printf("Infinity!\n");
        else printf("No solution!\n");
    }
    return 0;
}