枚举、前缀和、二分

题意：

有m种花，每种花数量无上限。
已知对于第i种花，第一次选收获a[i].
此后，再次选第i种花收获b[i].
现在要选n种花，请问收获的最大值是多少？
1 <= n <= 10^9 , 1 <= m <= 10^5 , 0 <= a[i],b[i] <= 10^9

分析：

这一题，乍一看很像动态规划类似背包问题。但是状态却很难表示。
因此，我并没有尝试动态规划。
下面给出我的想法：

我们直观地想想，我们应该如何拿花：

我们先对所有的a和所有的b进行一次排序：
假设排成这样（从大到小，数值相等a放在前面）
[a5,a4,a9,a1,b4,a7,b5,b6,b5,b9,a2。。。。。。]
我们很明显前四个应该选择a5,a4,a9,a1
然后到第五个b4
因为前面a4被选过了所以我们不需要考虑任何也可以选b4
并且因为b4比后面的花收获都高了，所以我们就把接下来的所有都选择为b4吧

这是很显然的！

但是倘若在前面a4并没有选到呢？

[a5,a9,a1,b4,a7,b5,a4,b6,b5,b9,a2。。。。。。]
b4 变成了第四个。
如此当我们遇到b4时就面临了分歧
1.舍弃b4向后选
2.到后面去先把a4选了,然后再回来以后都选b4

这两种分歧视具体情况没有最优的。
比如b4 = 5,a4 = 1, a7 = 4,b5 = 4（a5之前选过了） n = 5
如此我们应该选择2
而对于上面的例子，我们别的不变单单让n = 1000如此我们就一定要选择1了

这种分歧我们是无法判定的！！
因此采取贪心策略，贪心的向后选是肯定不行的！！！！！

但是通过上面的分析，我们可以观察到一个重点：
就是：
我们最后一般都会在一个b停下来，然后接下来的所有次数都选他。
尤其是在n>m，要选的数目大于种类时，这是一定发生的。

例外则是
[a1,a2,a3,a4,a6,a5,a7,b1,b4,b3,b6。。。。。] 从大到小排序
n = 6 <= m
唯有这种情况我们才可能选择雨露均沾式取法。
当然如果这样[a1,b1,a3,a4,a6,a5,a7,b2,b4,b3,b6。。。。。]
的话仍然不会发生

如此，我们找到了什么？
枚举点！！！！！
我们枚举每一个b点，计算以他作为最后选择的所得到的收获。
如果n<=m，我们再将前n大的a相加进行一次比较。
最后选出最大值
如此，便可以了！！！！！！

那么重点便是枚举一个bi点，如何计算以他作为最后选择的收获？
根据我们之前的分析，我要以bi为最后选择，那么之前比bi大的a我肯定都选了假设共x个
然后，要选择b，我需要先判断ai是否已经被选。
如果已经被选，那么接下来我就选择n-x个bi就好了
如果没有被选，那么我们先去选ai，然后再选n-x-1个bi

有了思路接下来就是编程的问题了，但是变成真的是个问题！！！

我打算先对a进行排序，从大到小
然后计算出其前缀和sum
如果n<=m的话，我们初始ans = sum[n]
再枚举bi时，我使用二分算法，找到bi在数组中的位置，也就是有多少个a比bi大
然后利用前缀和sum直接得出x个a的值
之后判断ai是否已经被选？这该如何判断？
其实只要判断对于每一朵花是a是否大于等于b就好了
因为若a>=b那么二分查找后a肯定在b的前面，也就是已经被选了！！
最后在于ans比较，留下大的
如此，我们成功全部解决了！

还需要的是，上述的需要的二分查找，因为我们是在一个递减序列中找第一个小于目标的元素
所以C++中自带的不是太好用，我重新写了一个二分查找。需要对二分查找模板足够的熟悉！！！！！

其实是很麻烦的。。。。。。

代码如下：

#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int max_m = 1e5 + 100;
pii a[max_m];
pii b[max_m];
int c[max_m];
ll sum[max_m];
bool jud[max_m];
ll n, m;

int bound(int l, int r, pii target) {
    while (l < r) 
    {
        int mid = (l + r) >> 1;
        if (a[mid] > target)l = mid + 1;
        else r = mid;
    }
    return r - 1;
}

int main() {
    ios::sync_with_stdio(0);
    int t;cin >> t;
    while (t--) {
        cin >> n >> m;
        fill(jud + 1, jud + 1 + m, false);
        for (int i = 1;i <= m;i++)
        {
            cin >> a[i].first;
            a[i].second = i;
            cin >> b[i].first;
            b[i].second = i;
            c[i] = a[i].first;
            if (a[i].first >= b[i].first)
                jud[i] = true;
        }
        sort(a + 1, a + 1 + m, greater<pii>());
        for (int i = 1;i <= m;i++)
        {
            sum[i] = sum[i - 1] + a[i].first;
        }

        ll ans = 0;
        if (n <= m)ans = sum[n];

        for (int i = 1;i <= m;i++)
        {
            ll comp = 0;
            int id = bound(1, 1 + m, b[i]);
            if (id >= n)continue;
            comp = sum[id];
            if (jud[b[i].second])
            {
                comp += b[i].first * ((ll)n - id);
            }
            el***p += c[b[i].second] + ((ll)n - id - 1) * b[i].first;
            }
            ans = max(ans, comp);
        }
        cout << ans << endl;
    }
}

注意！
有一行代码，不可或缺！

            int id = bound(1, 1 + m, b[i]);
            if (id >= n)continue;//!!!!!!!!!!

因为我们一共就要取n个，而在这里比bi大的a就已经大于等于n个了，所以我们是不可能取到bi的。在有的题目当中即使不注意这些鸡毛蒜皮的事情也无关紧要，但这里不一样。

            ll comp = 0;
            int id = bound(1, 1 + m, b[i]);
            if (id >= n)continue;
            comp = sum[id];
            if (jud[b[i].second])
            {
                comp += b[i].first * ((ll)n - id); //！！！！！！！1
            }
            el***p += c[b[i].second] + ((ll)n - id - 1) * b[i].first;//！！！！！！
            }

我们算入了sum[id]，id>=n，虽然后面的n-id是负的，但是无法保证他们加起来会小于ans，不给ans造成影响。

因此，如果你少了这句话，你将在第五个测试用例报错！！！！
滑稽。。。。。。

Codeforces Round #657 (Div. 2) C. Choosing flowers

枚举、前缀和、二分

题意：

分析：

代码如下：