zancun

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 100005;
int n;
int avai[maxn], need[maxn];
bool dfs(int cur, int u, int f, bool lap)
{
    if(cur == u && lap) return true;

    if(f + avai[cur] < need[cur]) return false;
    f = f+avai[cur]-need[cur];
    //cout << f << endl;
    if(cur == (u-1+n)%n && !lap) lap = true;
    if(dfs((cur+1)%n, u, f, lap)) return true;
    return false;
}

int solve()
{
    for(int i = 0; i < n; i++)
    {
        if(dfs(i, i, 0, false)) return i;
        //cout << i << endl;
    }
    return -1;
}

int main()
{
    //freopen("out.txt", "w", stdout);
    int T; scanf("%d", &T);
    for(int kase = 1; kase <= T; kase++)
    {
        scanf("%d", &n);
        int sum1, sum2;
        sum1 = sum2 = 0;
        for(int i = 0; i < n; i++)
            scanf("%d", &avai[i]), sum1 += avai[i];
        for(int i = 0; i < n; i++)
            scanf("%d", &need[i]), sum2 += need[i];
        printf("Case %d: ", kase);
        if(sum1 < sum2) printf("Not possible
");
        else
        {
            int flag = solve();
            if(flag == -1) printf("Not possible
");
            else printf("Possible from station %d
", flag+1);
        }
    }
    return 0;
}
原文地址:https://www.cnblogs.com/LLGemini/p/4792592.html