【cf1313B】B. Different Rules(贪心+构造)

传送门

题意:
现在有(n)个人参加两场比赛,已知你在两场比赛中的积分分别为(x,y),其他人的积分并不知道。
最终总的积分为(x+y)。现在想知道最终你的总排名最低和最高是多少。
定义一个人的排名比你低当且仅当其积分(a)不超过你的积分(b)

思路:
考虑使得最终总排名最高(这里说的高其实是指排名靠后),那么也就是我们想要尽量多的人积分和为(x+y)。那么可以如下构造积分:((1,x+y-1),(2,x+y-2),cdots,(x+y-1,1)),显然对((x,y))也在其中,那么最终答案即为(min(n,x+y-1))

现在考虑最终总排名最低(排名靠前),按照上面的思路,也就是尽量多的人分数和为(x+y+1),那么可以如下构造:((1,x+y),(2,x+y-1),cdots,(x+y,1))
注意到此时要分情况考虑:

  • (x+yleq n)时,排名为1。
  • 证明:可以直接构造((1,n),(2,n-1),cdots,(n,1)),此时当((x,y))不在这些对中时,不妨(xleq y),那么((x,n-x+1),(n-y+1,y))中,将((x,y))连起来剩下的对即为((n-y+1,n-x+1)),因为(n-x+1+n-y+1=2n-x-y+2>n+1>x+y)。所以此时排名为(1)
  • (x+y>n)时,排名为(x+y-n+1)
  • 证明:对于排名为(1)的选手而言,无论怎么配对,最后排名都会比你小;同样,对于排名为(2,3,cdots,x+y-n)的人来说,无论怎么配对,最后的积分都不会超过你。那么我们将这些人((1,1),(2,2),cdots,(x+y-n,x+y-n))配对。避免浪费资源,注意此时一定有(x,y>x+y-n),那么剩下的人都可以如第一种配对,所以答案为(x+y-n+1)

写起来的时候还要注意一些边角情况。
不过我写的时候没有直接这么构造,而是类似贪心那样去搞,就直接贴上我的代码吧。

/*
 * Author:  heyuhhh
 * Created Time:  2020/2/24 10:15:33
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << '
'; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;

int n, x, y;

int gao(int sum, int op) {
    int s = max(1, sum - n), t = min(n, sum - 1);
    int l = t - s + 1 - (s <= x && x <= t), r = t - s + 1 - (s <= y && y <= t);
    int res = min(l, r);
    l = n - t - (x >= sum), r = n - t - (y >= sum);
    if(op) {
        res += min(s - 1, l) + min(s - 1, r);
        l -= s - 1, r -= s - 1;
        if(l > 0 && r > 0) res += min(l, r);
    } else res += s - 1;
    return res;
}

void run(){
    cin >> n >> x >> y;
    int ans1 = n - gao(x + y + 1, 1), ans2 = gao(x + y, 0) + 1;
    cout << ans1 << ' ' << ans2 << '
';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    int T; cin >> T;
    while(T--) run();
    return 0;
}
原文地址:https://www.cnblogs.com/heyuhhh/p/12356573.html