8.26美团笔试五道题题解

T1

二分答案

经典二分答案题，二分答案天数mid 然后根据x和y计算最终成长值是否>=z

bool check(int mid){
    return 1ll*mid*x+1ll*mid/3*y>=z;
}
void solve(int u) {
    cin>>x>>y>>z;
    int l=0,r=1e9;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
}

T2

纯模拟，注意上取整即可

void solve(int u) {
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int k,c;
        cin>>k>>c;
        int cost=(c+k-1)/k;   //上取整
        for(int j=1;j<k;j++){
            int p;
            cin>>p;
            res[p]+=cost;
        }
    }
    for(int i=1;i<=m;i++)cout<<res[i]<<" ";
}

T3

贪心：维护一个大根堆，每次取出最大值和次大值进行操作(记得开long long)

void solve(int u) {
    cin>>n>>k;
    priority_queue<long long>heap;  //大根堆
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        heap.push(x);
    }
    while(k--){
        auto x=heap.top();heap.pop();
        auto y=heap.top();heap.pop();
        heap.push((x*y)%mod);heap.push(1);
    }
    ll res=0;
    while(heap.size()){
        res=(res+heap.top())%mod;
        heap.pop();
    }
    cout<<res<<endl;
}

T4

贪心：田忌赛马的思想，让a的最大值与b的最小值匹配，a的次大值与b的次小值匹配...虽然说b数组是固定，但其实是可以排序之后匹配的，这样代码会好写一写

void solve(int u) {
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
    sort(b,b+m);
    sort(a,a+n);
    int res=0,minnum=1e9;
    for(int i=0;i<n;i++){
        int x=a[i]+b[n-i-1];
        if(x<1||x>m){
            puts("No");
            return;
        }
    }
    puts("Yes");
}

T5

设s[i]为1~i的前缀和大小

如果(i,j]区间满足平均值为k 则有s[j]-s[i]=(j-i)*k

交换一下式子即有s[j]-j*k=s[i]-i*k

因此使用哈希表维护s[i]-i*k即可

int T, a[N],w[N],k,n;
int res=-1;
void solve(int u) {
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>w[i];
    map<long long,int>mp; 
    mp[0]=0;
    long long sum=0;
    for(int i=1;i<=n;i++){
        sum+=w[i];
        if(mp.count(sum-k*i)){
            res=max(res,i-mp[sum-k*i]);  //更新最大长度
        }
        else{
            mp[sum-k*i]=i;
        }
    }
    cout<<res<<endl;
}