首页 > 代码库 > Topcoder SRM646 DIV2 1000

Topcoder SRM646 DIV2 1000

题目大意:给你两个vector,一个代表队伍的得分,一个代表得分为这个得分的队伍的个数,假设每支队伍还有两次比赛没有进行,比赛的规则是赢一场得3分,输一场得0分,没有平的情况。已知这个队伍的目前得分让你求出来所有的球队打完最后一场,这个球队理论上的最好排名,注意可以和除了自己以外的任何一支队伍进行比赛,次数任意。

解题思路:显然排名高的话,这个球队这两次比赛一定得赢,所以主要分为3种情况:1,即使得分+6也不会超过的,这些球队即使全输也会在他们前面,所以我们让他们全赢,2,低于m的,这些球队即使赢了也就<= m+6,所以也没有影响,就让它们也赢,3,位于m+3< x <= m+6这些人赢一场就会超过m+6,先让大于m+6与<=m的去赢他们,然后剩下的之间相互赢每个人都只赢两场,就是对半分。再剩下的一定就会排在当前人的前面。

Problem Statement

 John and Brus are the managers of your football team. The team is taking part in a tournament. The tournament is almost over: each team still has exactly two matches to play (possibly both against the same opponent). Note that two different teams play in each match.

There are no ties in this tournament. Each match is played until one of the two teams wins. The winner of a match gets 3 points, the loser gets 0 points.

You are given an int yourScore: the number of points your team has scored so far. You are also given two vector <int>sscores and numberOfTeams that describe the other teams. For each valid i, there arenumberOfTeams[i] other teams that each have scored scores[i] points so far. Note that the total number of teams in the tournament is 1 + sum(numberOfTeams).

At the end of the tournament, teams will be ranked by the total number of points. Teams with the same number of points will be ranked according to their total score.

Given the above information, you are interested in the best possible (1-based) final rank of your team. Note that you do not know which matches are still to be played, so you assume the best possible combination of matches that is consistent with the given information.

In other words, you want to find the smallest X such that there exists a valid set of future match results that causes your team to end in X-th place. Note that your team‘s score can be arbitrarily good, so you may always assume that your team is placed above all other teams that have the same score as you.

Compute and return the X defined above.

Definition

 
Class:TheFootballDivTwo
Method:find
Parameters:int, vector <int>, vector <int>
Returns:int
Method signature:int find(int yourScore, vector <int> scores, vector <int> numberOfTeams)
(be sure your method is public)

Limits

 
Time limit (s):2.000
Memory limit (MB):256
Stack limit (MB):256

Notes

-The current scores given in yourScore and scores do not necessarily correspond to a valid game history. In particular, they do not have to be divisible by 3.

Constraints

-yourScore will be between 0 and 100,000, inclusive.
-scores will contain between 1 and 47 elements, inclusive.
-scores and numberOfTeams will contain the same number of elements.
-Each element of scores will be between 0 and 100,000, inclusive.
-Each element of numberOfTeams will be between 1 and 100,000, inclusive.

Examples

0) 
 
4
{7}
{1}
Returns: 1
There are two teams in the tournament. They play two games against each other. If your team wins both games it will be on the top of the scoreboard with 10 points.
1) 
 
1
{7}
{2}
Returns: 2
There are three teams. Your team has 1 point and each of the other two teams has 7 points. With three teams, the remaining matches are determined uniquely: each pair of teams must play a single match against each other. The best possible final result for your team is to place second with 7 points.
2) 
 
1
{7, 1}
{2, 1}
Returns: 1
There are four teams - two with 1 point each and two with 7 points each. If each 1-point team plays against each 7-point team and wins, each team will have 7 points in the end.
3) 
 
11
{5, 12, 17, 19, 99, 13, 15, 14}
{2, 4, 8, 2, 1, 3, 25, 3}
Returns: 18
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define eps 1e-10
///#define M 1000100
///#define LL __int64
#define LL long long
#define INF 0x7fffffff
#define PI 3.1415926535898
#define zero(x) ((fabs(x)<eps)?0:x)

using namespace std;

const int maxn = 2010;


int mp[maxn][maxn];


class TheFootballDivTwo
{
public:
    int find(int yourScore, vector <int> scores, vector <int> numberOfTeams)
    {
        int n = scores.size();
        int Min = 0;
        int Max = 0;
        int m = yourScore;
        int xp = 0;
        for(int i = 0; i < n; i++)
        {
            int x = scores[i];
            int y = numberOfTeams[i];
            if(x > m+6)
            {
                Min += y;
                xp += y;
            }
            if(x <= m) Min += y;
            if(m+4 <= x && x <= m+6) Max += y;
        }
        Max -= Min;
        Max -= 1;
        if(Max <= 0) return xp+1;
        Max += 1;
        Max /= 2;
        return xp+Max+1;
    }
};
int main()
{

    return 0;
}


Topcoder SRM646 DIV2 1000