首页 > 其他 > 详细

zancun

时间:2015-09-08 19:53:08      阅读:268      评论:0      收藏:0      [点我收藏+]
#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\n");
        else
        {
            int flag = solve();
            if(flag == -1) printf("Not possible\n");
            else printf("Possible from station %d\n", flag+1);
        }
    }
    return 0;
}

 

zancun

原文:http://www.cnblogs.com/LLGemini/p/4792592.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!