P4165 [SCOI2007] 组队详解

Cells · 2025-08-25 11:56:44 · 题解

思路

首先如果你没过可以再想想你是不是题读错了或者哪里想歪了。

设 H = minH, V = minV，由于 n \le 5000，很明显是在提醒正解的时间复杂度是 O(n ^ 2) 的，那么我们可以先枚举一个 H。

原式为：

A \times (h - H) + B \times (v - V) \le C\\ A \times (h - H) + Bv - BV \le C\\ A \times (h - H) - Bv - C \le BV\\ \frac{A \times (h - H) - Bv - C}{B} \le V

显然有：

\frac{A \times (h - H) - Bv - C}{B} \le V \le v

也就是说对于可以跑出每个球员能够入选的 v 的区间，那么只需要选择一个区间覆盖最多的点就可以了，使用差分数组进行维护。

给组大一点的样例。

Code

//# pragma GCC optimize("Ofast")
# include <bits/stdc++.h>
# define fr front
# define il inline
# define fir first
# define sec second
# define vec vector
# define it iterator
# define pb push_back
# define lb lower_bound
# define ub upper_bound
# define all(x) x.begin(), x.end()
# define mem(a, b) memset(a, b, sizeof(a))

# define lc (t[p].l)
# define rc (t[p].r)
# define ls(x) (x << 1)
# define rs(x) (x << 1 | 1)
# define lson ls(p), l, mid
# define rson rs(p), mid + 1, r

# define sqr(x) ((x) * (x))
# define bpc __builtin_popcount
# define lowbit(x) ((x) & (-(x)))
# define geti(x, i) (((x) >> (i)) & 1)
# define set1(x, i) ((x) | (1 << (i)))
# define set0(x, i) ((x) & (~(1 << (i))))

# define debug1(x) cerr << #x << " = " << x << " "
# define debug2(x) cerr << #x << " = " << x << "\n"
# define bug cerr << "--------------------------\n"

# define each1(i, x) for(auto (i) : (x))
# define each2(i, x) for(auto (&i) : (x))
# define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
# define pre(i, a, b) for(int i = (a); i >= (b); -- i)
# define G(i, h, u, ne) for(int i = (h[(u)]); i; i = (ne[(i)]))
# define reps(i, a, b, c) for(int i = (a); i <= (b); i += (c))
# define pres(i, a, b, c) for(int i = (a); i >= (b); i -= (c))
using namespace std;

using DB = double;
using LL = long long;
using LDB = long double;
using PII = pair<int, int>;
using ULL = unsigned long long;

const int N = 5e3 + 10, V = 1e4 + 10;
const int INF1 = 0x3f3f3f3f, INF2 = INT_MAX;
const LL INF3 = (LL)1e18, INF4 = 0x3f3f3f3f3f3f3f3f, INF5 = LLONG_MAX;

int n, a, b, c, sum, ans;
int h[N], v[N], pre[V];

vec<int> val;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> a >> b >> c;

    rep(i, 1, n){
        cin >> h[i] >> v[i];
        val.pb(h[i]);
    }

    sort(all(val));
    val.erase(unique(all(val)), val.end()); 

    each2(H, val){//去重枚举可以将10000降到5000，而且确实应该用存在的h 
        sum = 0;
        mem(pre, 0);

        rep(i, 1, n){
            if(H > h[i]) continue;//很明显 
            int d = ceil((DB)(a * (h[i] - H) + b * v[i] - c) / (DB)b);
            if(d > v[i]) continue;//根本没有合法区间 
            if(d < 0) d = 0;//看下面的输出调试，注意越界 
            pre[d] ++;
            pre[v[i] + 1] --;
//          cout << d << " " << v[i] + 1 << "\n";
        }

        rep(i, 1, 10000) pre[i] += pre[i - 1];
        rep(i, 1, n) ans = max(ans, pre[v[i]]);//只能是存在的v 
    }

    cout << ans;

    return 0;
}

離愁能有多痛？痛有多濃？當夢被埋在江南煙雨中，心碎了才懂…………

P4165 [SCOI2007] 组队 详解

思路

Code

P4165 [SCOI2007] 组队详解