ACM学习历程—UVALive 7147 World Cup（分类讨论 && 贪心）

题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5159

题目大意是就是n个人进行两两的比赛，胜一局得A分，平局B分，败局C分。

然后取前m名入围，求入围的人最小的可能分数以及被淘汰的人的最大的可能分数。

这题首先可以想到的是胜A负C和胜C负A的情况是一模一样的。

所以可以先考虑让A大C小。

然后开始分情况讨论：

（1)B最小

1·这种情况下全部平局的话，能让入围的人分数最小。

2·然后需要考虑被淘汰的人的最大的可能分数：

必然将这些人分成m+1+n-m-1

由于要让这个’1’的分数尽可能大，自然考虑让n-m-1个人全部负场淘汰。

这样前面m+1个人都先得到a*(n-m-1)分。

然后需要让这个’1’尽可能大的话，首先他可以和m其中一半的人打胜场，和另一半的人打负场，这比打平局合算。然后这一半的人再胜另一半的人，这种情况所有人分数平衡。

此时又得到m/2*(a+c)分。

最后如果m是奇数，那么最后一场打负场。

这样做，因为’1’最多只能胜m个人里面一半的人，否则他肯定不会是最后一名。

所以中间打一半胜一半负，而且最后m%2那一局不能胜。

此外c>b，所以考虑m%2那场负。

(2)B最大

1·这种情况下全部平局的话，能让被淘汰的人的分数最大。

2·然后需要考虑围的人最小的可能分数；

必然将这些人分成m-1+1+n-m

由于要让这个’1’的分数尽可能小，自然考虑让m-1个人全部胜场入围。

这样前面n-m+1个人都先得到c*(m-1)分。

然后需要让这个’1’尽可能小的话，首先他可以和n-m其中一半的人打胜场，和另一半的人打负场，这比打平局分数少。

此时又得到(n-m)/2*(a+c)分。

最后如果n-m是奇数，那么最后一场打胜场。

这样做，因为’1’最多只能负m个人里面一半的人，否则他肯定不会是第一名。

所以中间打一半胜一半负，而且最后(n-m)%2那一局不能负。

此外a<b，所以考虑(n-m)%2那场胜。

（3）剩余情况中2*b < a+c的：

为什么考虑这两者的关系，因为上面的讨论已经发现了微妙的联系。

1·考虑围的人最小的可能分数；

必然m-1+1+n-m

然后让前面的m-1个人都胜场入围，那么必然’1’首先需要败m-1场。

然后他需要胜过至少(n-m)里面的一半人，这种情况下由于一开始的2*b < a+c，他选择平局分数更小。

自然最后如果多一场选择平局，而不选择胜局。

2·考虑被淘汰的人的最大的可能分数：

自然需要先胜(n-m-1)个人，因为他们全部负场。

然后他跟前面的人打一半胜一半负，因为2*b < a+c。

最后多的一场m%2打平局，否则他将胜过一半人。

（4）最后一种情况和(3)类似了。

代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <set>

#include <map>

#include <vector>

#include <string>

#include <queue>

#define LL long long

#define MOD 1000000007

using namespace std;

int n, m, a, b, c;

LL mi, ma;

void input()

{

    scanf("%d%d", &n, &m);

    scanf("%d%d%d", &a, &b, &c);

    if (a < c) swap(a, c);

}

void work()

{

    if (b < a && b < c)

    {

        mi = (LL)b*(n-);

        ma = (LL)a*(n-m-);

        ma += (LL)m/*(a+c);

        ma += (LL)c*(m%);//

        return;

    }

    if (b > a && b > c)

    {

        ma = (LL)b*(n-);

        mi = (LL)c*(m-);

        mi += ((LL)n-m)/*(a+c);

        mi += (LL)a*((n-m)%);//

        return;

    }

    if (*b < a+c)

    {

        mi = (LL)c*(m-);

        mi += ((LL)n-m)*b;

        ma = (LL)a*(n-m-);

        ma += (LL)m/*(a+c);

        ma += (LL)b*(m%);//

        return;

    }

    else

    {

        mi = (LL)c*(m-);

        mi += ((LL)n-m)/*(a+c);

        mi += (LL)b*((n-m)%);//

        ma = (LL)a*(n-m-);

        ma += (LL)m*b;

        return;

    }

}

int main()

{

    //freopen("test.in", "r", stdin);

    int T;

    scanf("%d", &T);

    for (int times = ; times <= T; ++times)

    {

        input();

        work();

        printf("Case #%d: ", times);

        printf("%lld %lld\n", ma, mi);

    }

    return ;

}

巴特西

ACM学习历程—UVALive 7147 World Cup（分类讨论 && 贪心）

最新文章

热门文章