二分

二分应用

lower_bound(upper_bound)函数应用

题目链接：https://ac.nowcoder.com/acm/contest/84444/E

题意

有n种猫粮，第i种猫粮的营养值为,数量为,猫猫每一天可以吃任意数量和种类的猫粮，但每种猫粮只会吃一份。求k天内猫猫可以获得的最大营养值。

数据范围

题解

    易知，每个种类每天只能吃一次，显然，对于所有剩余的猫粮，每天都吃一次是得到最大营养值的最优解，不难想到，此时对答案的贡献就是所有存在猫粮的和！每过一天，所有猫粮的数量集体减一，直至所有猫粮的数量均为0；对所有猫粮按照数量为第一关键字进行结构体升序，那么每次对答案的贡献即为天数*后缀和！
    我们遍历数组并用前缀和pre[i]维护前i天的最大营养值，但是会产生一个问题：给出的数量值是离散的，而询问的值可能恰好夹在离散的数量（天数）之间？所以，我们可以借助二分函数寻找第一个小于其天数的“离散块”，再通过多余天数的贡献算出答案，设找到的第一个小于天数的值为s，则答案为pre[s]+(k-s)*suf。
    需要注意的是，由于数量值的范围极大，同时对应我们需要查询的天数，所以pre数组务必要使用map容器。时间复杂度为O(q * logN)，可以通过此题.

Code:

#include< bits/stdc++.h>
#define int long long
#define endl '\n' 
#define inf 1e15
using namespace std;
struct node{
    int a, b;
     bool operator<(const node ss)const{
        return b < ss.b;
    }
} s[100010];
int c[100010],suf[100010];
map< int,int> pre;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n, q;
    cin >> n;
    for (int i = 1; i <= n;i++)
        cin >> s[i].a;
    for (int i = 1; i <= n; i++)
    cin >> s[i].b;
    sort(s + 1, s + n + 1);
    for (int i = n; i >= 1;i--)
        c[i] = s[i].b, suf[i] = suf[i + 1] + s[i].a;
    pre[s[1].b] = suf[1] * s[1].b; //初始化，天数乘以后缀和
    for (int i = 2; i <= n;i++){
        if(s[i].b==s[i-1].b)
            continue;
        else{
            pre[s[i].b] = pre[s[i - 1].b];
            pre[s[i].b] += (s[i].b - s[i - 1].b) * suf[i];
        }
    }
    int tot = s[n].b;
    cin >> q;
    while(q--){
        int k;
        cin >> k;
        if(k>tot) //查询天数大于最高数量
            cout << pre[tot] << endl;
        else if(pre[k]) //查询天数已统计
            cout << pre[k] << endl;
        else{
            int pos = upper_bound(c + 1, c + n + 1, k) - c;
            int ans = pre[s[pos - 1].b] + (k - s[pos - 1].b) * suf[pos];
            cout << ans << endl;
        }
    }
    return 0;
}