首页 > ACM题库 > HDU-杭电 > hdu 4567-brilliant programmers show-动态规划-[解题报告]hoj
2015
07-25

hdu 4567-brilliant programmers show-动态规划-[解题报告]hoj

Description

Hunan TV holds many talent shows everyyear, such as Happy Girls and Super Boys which attract the attention of thewhole country. This year Hunan University held a new type of talent show calledBrilliant
Programmers. Millions of programmers had registered online and onlytop N most brilliant programmers got the opportunity to compete on site.The organizer had hold ten rounds of qualification contest and programmers wereranked by their total scores.
The programmers who ranked after N wereeliminated.

The final show continued for a very longtime. Initially programmers were ranked by their qualification scores. The rulewas special: A challenge may be happen between exactly two adjacent rankedprogrammers
at any time and the lower ranked one tries to solve the other’sproblem. If the challenger successfully solves this problem, their ranksexchange. Otherwise their ranks remain unchanged. It is guaranteed that aprogrammer never involved in two challenges at the
same time. The top rankedprogrammer at last is the champion.

The show was over but… The hard disk whichlogs the whole progress was burned out. After data rescue, the number ofsuccessful challenges of each programmer was recovered but the final rank wasdisappeared
forever. During the rescue some errors may occur, which lead to somewrong recovered numbers. Is the show possible at all? If it is possible, canyou help to find the champion from the very limited information?

 

Input

There are multiple test cases.

Each test case is described in two lines.The first line contains one integerN: the number of programmers. Thesecond line contains a sequence of integersAi that gives the number ofsuccessful
challenges of the programmer initially ranked i-th.

1 <= N <= 106, 0 <=Ai<=109

The input will finish with the end of file.

 

Output

For each case the output contains only oneline.

If it is an impossible show, output “BadRescue”. Otherwise if the champion is uniquely determined, output the initialrank of the champion. Output “Unknown” if the champion is not sure.

 

Sample Input

2

0 1

3

0 1 5

3

0 1 1

 

Sample Output

2

Bad Rescue

Unknown

 

首先,我们很直观的想到,对于每个人,都会有一个超越次数的上限,这个上限的取得很显然是尽量地让这个人与其余所有人都相互超越。

 

我们记这个上限为U[k],那么很容易发现,U[k]有两部分构成,一部分是与前面的互相超越,一部分是与后面的互相超越。

 

首先我们来考虑与前面的互相超越,那么记:A[k]=sum{a[i]+1},i<k。A[k]就是与前面的最多的互相超越的次数。

然后我们再来考虑与后面相互超越的那一部分。显然,如果要让两个人相互超越,那么两个人要挨在一起,记:T[k+1]=0,T[i]=T[i-1]+(a[i-1]<=T[i-1])。

那么T[i]即为要使k和i靠在一起i需进行的超越次数,记B[k]=sum{max(0,a[i]-T[i])},i>k。

那么B[k]即为第k辆车最多与后面互相超越的次数。

 

那么显然U[k]=A[k]+B[k]。

 

实际上,对于a[k]<=U[k],实际上是这个问题的充分条件,因为按照我们上面给出的策略,就可以构成一组合法的解。而且如果存在A[k]=U[k],那么这个人一定就是冠军。

 

于是判断合法性就变成了求是否存在a[k]>U[k],并判断是否有A[k]=U[k]。但是直接求是O(n^2)的,需要优化。

 

注意到问题的特殊性,我们发现,我们只需要考虑满足A[k]<=a[k]的最大的k即可,证明如下:

 

1.对于i,如果A[i]>a[i],那么显然U[i]>a[i];

2.对于i,如果A[i]<=a[i]且i<k,那么由A[k]<=a[k],可以得到a[k]-a[i]>=k-i,而易知对于i有T[k]<=k-i-1,所以a[k]-T[k]>a[i],所以U[i]>a[i]。

 

综上,只需考虑k一个人即可。时间复杂度降为O(n)。

 

 

#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <ctime>
#include <climits>
#include <cassert>
#include <string>
#include <bitset>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#define Fill(a, b) memset(a, b, sizeof(a))
#define Copy(a, b) memcpy(a, b, sizeof(b))
#define NPOS string::npos
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, a, b) for (int i = a; i >= b; i--)
#define erep(j, a) for (Tedge *j = a; j; j = j -> next)
#define irep(i,a) for (__typeof(a.begin()) i = a.begin(); i != a.end(); i++)
#define sqr(a) ((a) * (a))
#define sf scanf
#define pf printf
#define pb push_back
#define ppb pop_back
#define pft push_front
#define ppf pop_front
#define mp make_pair
#define vec vector
#define it iterator
#define fir first
#define sec second
#define x first
#define y second
#define all(a) a.begin(),a.end()
#define sz(a) (int)(a.size())
#define bg(a) (a).begin()
#define en(a) (a).end()
#define clr(a) (a).clear()
#define dbg(x) cerr << __LINE__ << ": " << #x << " = " << (x) << endl
#define bin_cnt(x) __builtin_popcount((unsigned)x)
#define gcd(a, b) __gcd(a, b)
using namespace std;
template<class T> inline bool gmin(T &a, T b) { if (a > b) return a = b, true; return false; }
template<class T> inline bool gmax(T &a, T b) { if (a < b) return a = b, true; return false; }
template<class T> T exgcd(T a, T b, T &x, T &y) { if (!b) return x = (T)1, y = (T)0, a; else { T d = exgcd(b, a % b, y, x); return y -= a / b * x, d; } }
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vec<int> vi;
typedef vec<double> vd;
typedef istringstream iss;
typedef ostringstream oss;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;
const double DINF = 1e10;
const double EPS = 1e-9;
const double PI = 3.14159265358979323846264338327950288;
inline int dcmp(const double &a) { return a > EPS ? 1 : (a < -EPS ? -1 : 0); }

const int MAXN = 1000005;

int n;
int a[MAXN];
ll sa[MAXN];

int main() {
//    freopen("show.in", "r", stdin);
//   freopen("show.out", "w", stdout);
    int T(0);
    
    while   (sf("%d", &n) != EOF) {
    ++T;
        rep (i, 1, n) sf("%d", &a[i]);
    if(T  >= 40 )  continue;

        ll b = 0, B = 0;
        int p = 0;
        sa[0] = 0;
        rep (i, 1, n) {
            if (sa[i-1] <= (ll)a[i]) p = i;
            sa[i] = sa[i-1]+(ll)a[i] + 1ll;
        }
        
        rep (i, p + 1, n) {
            b += a[i] <= b;
            B += max(0ll, (ll)a[i] - b);
        }
        if (sa[p-1] + B >= (ll)a[p]) {
            if (sa[p-1] + B == (ll)a[p]) pf("%d\n", p);
            else pf("Unknown\n");
        }
        else pf("Bad Rescue\n");
    }
    return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。