f[j]表示当威望为j时 最少需要的代价(拉拢的选民)
bag为当前的威望值上限
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll f[N];
int bag, n;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for(int i = 1;i <= n;i++){
        int a, b, c;
        cin >> a >> b >> c;
        bag += c;
        int w = max(0, (b - a + 1) / 2);
        for(int j = bag;j >= c;j--){
            f[j] = min(f[j], f[j - c] + w);
        }
    }

    ll ans = 0x3f3f3f3f3f3f3f3f;
    for(int i = (bag + 1) / 2;i <= bag;i++){
        ans = min(ans, f[i]);
    }
    cout << ans;

    return 0;
}