腾讯算法第三次笔试

tx 是真的难的啊 100,40,100,0,0

第一题排序即可

#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>
#include <string>
#include <set>
#include <queue>
#include <climits>
#include <unordered_set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <initializer_list>
#include <typeinfo>
#include <map>
using namespace std;
typedef  long long LL;
const int mod = 1e9+7;
const int inf = 0x7f7f7f7f;
#define _for(i,l,r) for(LL i=(l);i<(r);i++)
int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
vector<LL> x,y,ans;
int main() {
    LL n,m;
    scanf("%lld%lld",&n,&m);
    _for(i,0,n){
        LL c;
        scanf("%lld",&c);
        x.push_back(c);
    }
    _for(i,0,m){
        LL c;
        scanf("%lld",&c);
        y.push_back(c);
    }
    sort(x.begin(),x.end());
    sort(y.begin(),y.end());
    if(x.size() >= 4){
        ans.push_back(x[0] * y[0]);
        ans.push_back(x[0] * y[m -1]);
        ans.push_back(x[1] * y[0]);
        ans.push_back(x[1] * y[m -1]);

        ans.push_back(x[n - 1] * y[0]);
        ans.push_back(x[n - 1] * y[m -1]);
        ans.push_back(x[n - 2] * y[0]);
        ans.push_back(x[n - 2] * y[m -1]);
    }else{
        for(int i=0;i<x.size();i++){
            ans.push_back(x[i] * y[0]);
            ans.push_back(x[i] * y[m - 1]);
        }
    }
    sort(ans.begin(),ans.end());
    cout << ans[(int)ans.size() - 2] << endl;
    return 0;
}

2 第二题

#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>
#include <string>
#include <set>
#include <queue>
#include <climits>
#include <unordered_set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <initializer_list>
#include <typeinfo>
#include <map>
using namespace std;
typedef  long long LL;
const int mod = 1e9+7;
const int inf = 0x7f7f7f7f;
#define _for(i,l,r) for(LL i=(l);i<(r);i++)
int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
vector<LL> data;
int main() {
    LL n;
    scanf("%lld",&n);
    _for(i,0,n){
        LL x;
        scanf("%lld",&x);
        data.push_back(x);
    }
    sort(data.begin(),data.end());
    LL ans = 0;
    for(LL i = n - 1;i >= 0;i--){
        if(data[i] > 0){
            if(data[i] % 2==0){
                LL index = lower_bound(data.begin(),data.end(),data[i] /2) - data.begin();
                ans += max(0LL,i - index);
                LL k = lower_bound(data.begin(),data.end(),- data[i] / 2) - data.begin();
                index = lower_bound(data.begin(),data.end(), - data[i] * 2) - data.begin();
                ans += max(0LL,k - index);
            }else{
                LL index = lower_bound(data.begin(),data.end(),data[i] /2 + 1) - data.begin();
                ans += max(0LL,i - index);
                LL k = lower_bound(data.begin(),data.end(),- data[i] / 2 - 1) - data.begin();
                index = lower_bound(data.begin(),data.end(), - data[i] * 2) - data.begin();
                ans += max(0LL,k - index);
            }
        }else if(data[i] < 0){
            LL index = lower_bound(data.begin(),data.end(),data[i] * 2) - data.begin();
            ans += max(0LL,i - index);

        }else{
            ans += n - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

3 维护一个小根堆即可

#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>
#include <string>
#include <set>
#include <queue>
#include <climits>
#include <unordered_set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <initializer_list>
#include <typeinfo>
#include <map>
using namespace std;
typedef  long long LL;
const int mod = 1e9+7;
const int inf = 0x7f7f7f7f;
#define _for(i,l,r) for(LL i=(l);i<(r);i++)
int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
vector<pair<LL,LL>> data;
priority_queue<LL,vector<LL>,greater<LL>>sum;
int main() {
    LL n,k;
    scanf("%lld%lld",&n,&k);
    _for(i,0,n){
        LL x,y;
        scanf("%lld%lld",&x,&y);
        data.push_back(make_pair(y,x));
    }
    sort(data.begin(),data.end());
    LL tmp = 0;
    LL ans = LLONG_MIN;
    for(int i=(int)data.size() - 1;i >= 0;i--){
        if(sum.size() < k){
            sum.push(data[i].second);
            tmp += data[i].second;
            ans = max(ans, tmp * data[i].first);
        }else{
            LL top = sum.top();
            if(data[i].second > top) {
                sum.pop();
                tmp -= top;
                sum.push(data[i].second);
                tmp += data[i].second;
            }
            ans = max(ans, tmp * data[i].first);
        }
    }
    cout << ans << endl;
    return 0;
}

#笔试题目##腾讯##算法工程师#