[UVA][ad-hoc] 11093 - Just Finish it up＠Morris' Blog

2013-05-29 15:29:31| 人氣1,336| 回應0 | 上一篇 | 下一篇

[UVA][ad-hoc] 11093 - Just Finish it up

推薦 0 收藏 0 轉貼0 訂閱站台

I I U P C 2 0 0 6
Problem J: Just Finish it up
Input: standard input Output: standard output

Along a circular track, there are N gas stations, which are numbered clockwise from 1 up to N. At station i, there are p_i gallons of petrol available. To race from station i to its clockwise neighbor one need q_i gallons of petrol. Consider a race where a car will start the race with an empty fuel tank. Your task is to find whether the car can complete the race from any of the stations or not. If it can then mention the smallest possible station i from which the lap can be completed.
Input
First line of the input contains one integer T the number of test cases. Each test case will start with a line containing one integer N, which denotes the number of gas stations. In the next few lines contain *2N integers. First N integers denote the values of p_is (petrol available at station i), subsequent N integers denote the value of q_i**s (amount of patrol needed to go to the next station in the clockwise direction).
Output
For each test case, output the case number in the format “Case c: ”, where c is the case number starting form 1. Then display whether it is possible to complete a lap by a car with an empty tank or not. If it is not possible to complete the lap then display “Not possible”. If possible, then display “Possible from station X”, where X is the first possible station from which the car can complete the lap.
Constraints
- T < 25 - N < 100001
Sample Input	Output for Sample Input
2 5 1 1 1 1 1 1 1 2 1 1 7 1 1 1 10 1 1 1 2 2 2 2 2 2 2	Case 1: Not possible Case 2: Possible from station 4

Problemsetter: Md. Bahlul Haider Judge Solution: Istiaque Ahmed

題目描述：
一個環狀跑道, 接著每個站要前往下一個站都會消耗 qi 的油量, 而在這個站也會獲得 pi 的油量,
問能不能從一個點出發繞一圈？如果可以找一個字典順序最小的編號。

題目解法：
把問題轉換一下，將每個站 pi-qi，如果全部總合小於 0 代表 impossible，
接著試圖搜索一開始的起站，這裡不能進行 O(n*n) 的枚舉量 (雖然有很多剪枝或許不會那麼慘)
這裡可以做到 O(n) 的，假使枚舉起點 st, 則到達一個另一個點時 ed 無法進行下去,
那麼我們將 st = ed, 那麼每個點的出入次數都只有 1, 因此整個算法是 O(n)
仔細思考一下, [st, mid, mid+1, ..., ed]
可以保證 [st, mid] > 0 那麼更不可能存在 [mid+1, ..., ed] // 起點可能為 mid+1
st-ed 中間任何一點都不可能，只會負更大。

#include <stdio.h>
int p[100005], q[100005];
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int n, testcase, cases = 0;
    int i, j, k;
    int *a, *b;
    ReadInt(&testcase);
    //scanf("%d", &testcase);
    while(testcase--) {
        ReadInt(&n);
        //scanf("%d", &n);
        a = p, b = q;
        for(i = 0; i < n; i++) {
            ReadInt(a), a++;
            //scanf("%d", p+i);
        }
        for(i = 0; i < n; i++) {
            ReadInt(b), b++;
            //scanf("%d", q+i);
        }
        a = p, b = q;
        int sum = 0;
        for(i = 0; i < n; i++) {
            sum += (*a) - (*b);
            a++, b++;
        }
        printf("Case %d: ", ++cases);
        if(sum < 0) {
            puts("Not possible");
            continue;
        }
        for(i = 0; i < n; i++) {
            j = i, sum = 0, k = 0;
            a = p+j, b = q+j;
            while(sum >= 0) {
                sum += *a - *b;
                j++, k++, a++, b++;
                if(j >= n) j = 0, a = p, b = q;
                if(k == n) break;
            }
            if(k == n && sum >= 0) {
                printf("Possible from station %d\n", i+1);
                break;
            }
            if(j < i)   break;
            i = j-1;
        }
    }
    return 0;
}
/*
100
9
1 3 1 4 2 1 2 3 2
2 2 1 3 1 3 1 1 1
5
2 6 7 1 1
3 7 1 1 1
6
1 8 9 6 4 1
9 1 1 2 3 2
7
13 1 2 1 3 1 2
1 2 3 1 14 3 1
6
1 2 3 4 1 4
12 3 2 1 2 1
5
3 4 4 5 6
2 1 1 14 1
*/

我要檢舉

#11093#Just Finish it up

台長： Morris

您可能對以下文章有興趣

c112. Optimal Array Multiplication Sequence

[UVA] 11835 - Formula 1

[UVA] 11131 - Close Relatives

[UVA][EulerianGraph] 291 - The House Of Santa Claus

人氣(1,336) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 12150 - Pole Position
此分類上一篇:[UVA] 467 - Synching Signals

回應(0)

[UVA][ad-hoc] 11093 - Just Finish it up

Sample Input

您可能對以下文章有興趣