求解释 二分 + 贪心不行 %%%%
查看原帖
求解释 二分 + 贪心不行 %%%%
757864
ruye楼主2024/4/27 17:48
#include <bits/stdc++.h> // By Lucky Ox
#define int long long
#define endl "\n"
#define pii pair<int, int>
#define PI atan(1.0) * 4
using namespace std;
using i128 = __int128;
typedef long long ll;
const long long mod = 1000000000000002493, INF = 0x3f3f3f3f3f3f3f3f;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int lcm(int x, int y) { return x * y / gcd(x, y); }
int q_pow(int a, int k, int mod) { int res = 1; while (k) { if (k & 1) res = res * a % mod; k >>= 1; a = a * a % mod; } return res; }
int len_10(int x) { int len = 0; while(x) { x /= 10; len ++ ; } return len;}
int len_2(int x) { int len = 0; while(x) { x /= 2; len ++ ; } return len;}
// n / m上取整 (n + m - 1) / m 

const int N = 1e2 + 10;
int n, w, f;
int s[N];

int check(int mid) {
    int sw = w * mid, sf = f * mid;

    for(int i = 1; i <= n; i ++ ) {
        if(sw > sf) swap(sw, sf);
        if(sw >= s[i]) {
            sw -= s[i];
        } 
        else if(sf >= s[i]) {
            sf -= s[i];
        }
        else return 0;
    }
    return 1;
}
void solve() {
    cin >> w >> f >> n;
    int sum = 0;
    for(int i = 1; i <= n; i ++ ) cin >> s[i], sum += s[i];
    
    sort(s + 1, s + n + 1, greater<int>());

    int l = 1, r = (sum / (w + f)) + 10;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid - 1;
        else l = mid + 1;
    }
    cout << l << endl;
}

void init() {

}

signed main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cout << fixed << setprecision(10);
    init();
    int T = 1;
    cin >> T;
    while (T -- ) solve();
    return 0;
}

2024/4/27 17:48
加载中...