Codeforces Round #657 (Div. 2).C

• 题意

  • 给你 \(m\) 种花，在收到第 \(i\) 种类型的花后，幸福度会增加 \(a_i\)，在收到每一朵连续的这种类型的花后，幸福度会增加 \(b_i\) ，也就是说如果收到 \(x_i\) 种类型为 \(i\) 的花，幸福度就会增加 \(a_i + (x_i-1)*b_i\) ，现在你可以得到 \(n\) 朵花，你需要求出能达到的多大的幸福度是多少。

• 解析

  • 因为 \(n \leq 1e9\) ，所以 \(dp\) 肯定是行不通的，那就基本上只能考虑贪心。这个题刚开始还是很容易想到用贪心的方法，能想到的策略也有很多，我记得我听过一句话

    想到一个贪心策略是很简单的，但是证明一个贪心策略是很难的

  • 刚开始可能会想，\(a_i\) 最大的会不会一定要拿，或者 \(b_i\) 最大的要不要优先考虑

    ------
    100 2
    2 1
    1 100
    ------
    2 3
    8 1
    7 1
    6 2
    ------
    

  • 通过这两组样例就知道之前想的两个贪心策略都是错误的。

  • 经过思考后就会发现，可能的情况是在太多，如果直接贪心完全无法保证结果最大。

  • 那么这时候就要考虑先枚举一些东西。

  • 我们先想想解的形式。

    • 在 \(n \leq m\) 时，有可能会出现只选择，前 \(n\) 大的 \(a_i\) ，即按照 \(a\) 排序后，就取 \(a_1\)~ \(a_n\) 的和为一种可能的答案 ( 这是一种没有花选了多个的情况 )
    • 接下来考虑某一种花选了多个的情况，其他某些花就一种或者一种也没有
      1. 只可能有一种花选了多个，即不可能有第二种花同样有多个
      2. 若第 \(i\) 种花选了多个，那么比 \(b_i\) 大的 \(a_j\) 一定都拿了，并且比 \(b_i\) 小的 \(a_j\) 均没拿
      3. 因为第 \(i\) 种花选了多个，那么无论 \(a_i\) 多大都要选。

  • 这其实就是全部可能的解了，第一种情况很好写，现在直接想第二种情况。

  • 虽然这个题是贪心，但不代表不能枚举，所以我们如果枚举第 \(i\) 种花选了多个，按照上述规则找到一个可行解，只要找到所有的取最大值即可。

  • 那么现在选了第 \(i\) 种，该如何快速得到比 \(b_i\) 大的 \(a_j\) 的和呢？

  • 我们将 \(a\) 先排序，同时也将 \(b\) 排序 ( 分开存且均从大到小 )

  • 由于 \(b_i \ge b_{i+1}\) 所以所有比 \(b_{i+1}\) 大的 \(a_j\) 一定包含了所有比 \(b_i\) 大的，由于 \(a\) 也是有序的，那么只需要将在 \(b_i\) 与 \(b_{i+1}\) 范围内的 \(a\) 加进和即可 ( 记得统计 \(a_i\) 是否被包括进和里，也可通过 \(a_i\) 和 \(b_i\) 的大小关系判断，如果 \(a_i \ge b_i\) 那么被算进和了) ，还需要注意 只能选 n 个数！

• 代码

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const int Maxn = 1e5+10;
const int Inf = 0x7f7f7f7f;
const int Mod = 1e9+7;
 
struct Flower1{
    int a,pos;
}f1[Maxn];
struct Flower2{
    int b,pos,a;
}f2[Maxn];
 
bool cmpa(Flower1 a,Flower1 b){
    return a.a > b.a;
}
bool cmpb(Flower2 a,Flower2 b){
    return a.b > b.b;
}
 
bool vis[Maxn];
 
int main(){
    int T;
    scanf("%d",&T);
    while( T-- )
    {
        int n,m;
        scanf("%d %d",&n,&m);
        for(int i=1;i<=m;i++)
            scanf("%d %d",&f1[i].a,&f2[i].b), f1[i].pos = f2[i].pos = i, f2[i].a = f1[i].a;
        // 排序
        sort(f1+1,f1+1+m,cmpa);
        sort(f2+1,f2+1+m,cmpb);
        ll ans = 0,Sum = 0;
        //  处理第一个解的情况
        if( n <= m )
            for(int i=1;i<=n;i++)  ans += f1[i].a;
        for(int j=1,i=1;j<=m;j++)
        {
            // 将比 f2[j].b 大的 a 算进和
            while( i <= n && i <= m && f1[i].a >= f2[j].b )
            {
                Sum += f1[i].a;
                vis[f1[i].pos] = true;
                i++;
            }
            //  只能选 n 个
            if( i == n+1 )  break;
            if( vis[f2[j].pos] )  //  f2[j].a >= f2[j].b
                ans = max(ans,Sum + 1ll*f2[j].b*(n-i+1));
            else 
                ans = max(ans,Sum + 1ll*f2[j].a + 1ll*f2[j].b*(n-i));
        }
        printf("%lld\n",ans);
        for(int i=1;i<=m;i++)  vis[i] = false;
    }
    return 0;
}

Codeforces Round #657 (Div. 2).C

原文：https://www.cnblogs.com/HexQwQ/p/13341913.html