C++中的二分查找问题解决

二分查找真的很好用
就是说有一点绕
但是解体的效率还是很高的可能有机会遇到一些问题
本人写的一般所以只个方法一般不用

我想先排序 ，依次算出 (n-i)*ai， 取最大。

二分法呢？

二分查找

#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
long long n,max_,lower,max_money;
long long cows[MAXN];
int main(){
        cin>>n;
        for(int i=1; i<=n; i++) {
                long long temp;
                cin>>temp;
                cows[temp]++;
        }
        max_ = 0;
        lower = 0;
        for(int i=1; i<=MAXN; i++) {
                if(!cows[i]) continue;
                if(!(n-lower)) break;
                long long t = ((long long) (n-lower) * i);
                if(t > max_){
                        max_ = t;
                        max_money = i;
                }
                lower += cows[i];
        }
        cout<<max_<<" "<<max_money;
        return 0;
}

或贪心


#include <bits/stdc++.h>
using namespace std;

int n;
long long c[100001], res = 0, resc = 1ll << 60, rest = 0;

int main() {
        cin>>n;
        for (int i = 1; i <= n; ++i) {
                cin>>c[i];
        }
        sort(c + 1, c + n + 1);
        for (int i = 1; i <= n; ++i) {
                if (c[i] * (n - i + 1) > res) {
                        res = c[i] * (n - i + 1);
                }
        }
        for (int i = 1; i <= n; ++i) {
                if (res == c[i] * (n - i + 1)) {
                        resc = min(resc, c[i]);
                }
        }
        printf("%lld %lld", res, resc);
       return 0;
}

哇