题解 | Educational Codeforces Round 141 C. Yet Another Tournament 题目链接

题意:

  1. n+1个人(有n个电脑和你)参与单循环比赛,最后以胜利数量排名,若胜利数量相同则排名相同
  2. 电脑标记为1-n,标记大的电脑打标记小的电脑必赢.
  3. 你有k的精力,打赢标记为i的电脑需要消耗a[i]点
  4. 问你最后最好的情况排第几

思路:

  1. 既然按照胜利数量排名次,首先想到贪心看看最多能赢几个人
  2. 在你不参与的情况下,电脑的获胜数量分别为0 1 2 3 4 ... n,假设自己可以赢3场,就要考虑哪些电脑输给你或者赢了你会影响你的排名
  3. 首先原本胜利场数小于3的机器人不会撼动你的位置,因为即使她们赢了你最多跟你同胜利数,同胜利数排名一样的,可以说电脑排名前进了一名,但是你没有动
  4. 再考虑大于3的机器人,你的胜利数量已经定下来比她们小了,他跟你的比赛关系已经无所谓了,赢了你他赢你更多罢了,输了也比你强
  5. 得到结论,贪心后仅仅考虑你能否战胜同样胜利数为3的机器人即可

具体步骤:

  1. 贪心求你最多赢几场
  2. 计算如果赢了跟你胜场数一样的机器人还能否赢这么多场(暴力或者数学公式都可,题解代码用的公式)

tips:步骤第二步公式推导思路:贪心时计算花费了多少精力sum,在你已经战胜的电脑里挑出来一个需要最大精力的max,计算sum-max+a[和你获胜一样的电脑]是否小于等于k即可(计算时特判较多,并不是很推荐),推荐直接贪心,不会TLE,而且也不用考虑pair乱七八糟的特性

#define forn(i, n) for (int i = 1; i <= int(n); i++)

bool cmp(pair<ll, ll>x, pair<ll, ll>y) {
    return x.second < y.second;
}

void solve() {
    cin >> n >> k;
    forn(i, n)cin >> x[i],y[i].second=x[i],y[i].first=i,z[i]=0;
    z[n + 1] = 0;
    sort(y + 1, y + 1 + n,cmp);
    ll cnt = 0;//胜利次数
    ll ans = 0;//消耗精力
    y[0] = { 0,-100000 };//用于倒数第一时候的特判,写在19行的if里面也行 换成cnt==0输出n+1
    forn(i, n) {
        if (ans + y[i].second <= k)ans += y[i].second,z[y[i].first]=1, cnt++;
        else break;
    }
    if (cnt!=n&&(z[cnt + 1] == 1 || x[cnt + 1] + ans - y[cnt].second <= k))cout << n - cnt << endl;
    else cout << n - cnt + 1 << endl;
}