贪心法

#include <iostream>
#include <algorithm>
using namespace std;
struct Act { int s, e; };
bool cmp(Act a, Act b) { return a.e < b.e; }
int main() {
    int n; cin >> n;
    Act a[1005];
    for(int i=0;i<n;i++) cin >> a[i].s >> a[i].e;
    sort(a, a+n, cmp);
    int cnt=0, last=0;
    for(int i=0;i<n;i++)
        if(a[i].s >= last) { cnt++; last = a[i].e; }
    cout << cnt << endl;
    return 0;
}

#include <iostream>
#include <queue>
using namespace std;
int main() {
    int n; cin >> n;
    priority_queue<int,vector<int>,greater<int>> pq;
    for(int i=0;i<n;i++){int x;cin>>x;pq.push(x);}
    long long ans=0;
    while(pq.size()>1){
        int a=pq.top();pq.pop();
        int b=pq.top();pq.pop();
        ans+=a+b; pq.push(a+b);
    }
    cout << ans << endl;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n; cin >> n;
    int t[1005];
    for(int i=0;i<n;i++) cin >> t[i];
    sort(t, t+n);  // 短作业优先
    long long total=0, sum=0;
    for(int i=0;i<n;i++){
        sum += t[i];
        total += sum;
    }
    cout << total << endl;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
struct Seg { int l, r; };
bool cmp(Seg a, Seg b) { return a.l < b.l; }
int main() {
    int n, M; cin >> n >> M;
    Seg s[10005];
    for(int i=0;i<n;i++) cin >> s[i].l >> s[i].r;
    sort(s, s+n, cmp);
    int cnt=0, cover=0, i=0;
    while(cover < M) {
        int maxR = cover;
        while(i < n && s[i].l <= cover) {
            maxR = max(maxR, s[i].r);
            i++;
        }
        if(maxR == cover) { cout << -1; return 0; }
        cover = maxR;
        cnt++;
    }
    cout << cnt << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <cstdlib>
#include <functional>
#include <algorithm>
using namespace std;

int main() {
    int a[] = {3, 3, 2, 2, 2};
    int n = 5, sum = 0;
    for (int i = 0; i < n; i++) sum += a[i];

    // 方法一：贪心——从大到小，每次把木棍放进当前较短的一组
    vector<int> v(a, a + n);
    sort(v.begin(), v.end(), greater<int>());
    int g1 = 0, g2 = 0;
    for (int i = 0; i < n; i++) {
        if (g1 <= g2) g1 += v[i];
        else          g2 += v[i];
    }
    cout << "贪心分组: " << g1 << " vs " << g2
         << "   差 = " << abs(g1 - g2) << endl;

    // 方法二：0/1 背包 DP——dp[j] 表示能否凑出长度和恰好为 j
    vector<bool> dp(sum + 1, false);
    dp[0] = true;
    for (int i = 0; i < n; i++)
        for (int j = sum; j >= a[i]; j--)          // 必须倒着更新
            if (dp[j - a[i]]) dp[j] = true;

    int best = 0;
    for (int j = sum / 2; j >= 0; j--)             // 找不超过一半的最大可达和
        if (dp[j]) { best = j; break; }

    cout << "最优分组: " << best << " vs " << sum - best
         << "   差 = " << sum - 2 * best << endl;
    return 0;
}

struct Minister {
    long long L, R;
};
bool cmp(Minister a, Minister b) {
    return a.L * a.R < b.L * b.R;  // 按 L×R 升序
}