讨论/《美团 2021 届秋季校园招聘笔试真题》 - 小团的默契游戏/
《美团 2021 届秋季校园招聘笔试真题》 - 小团的默契游戏
共 4 个回复

首先,这道题根本没大数据
其次,没一组数据m大于n
然后,我最开始思路出错,只统计了两边的情况能过9组数据
数据出的够失败的
出题人自己会做吗
以下代码大数据以对拍,无误,1s内得结果

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,mi=1e9,mx,ans;
set<int>s;
set<int>::iterator it,tmp;
void add(int i){
    ans+=*it;
    tmp=it;it++;
    if(it!=s.end()&&*tmp<i)ans+=*it-*tmp;
    it=tmp;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int i,k,las=0;
    cin>>n>>m;
    vector<bool>h(n+1);
    vector<int>l(n+1),r(n+1),R(n+1);
    for(i=1;i<=n;i++){
        cin>>k;mi=min(k,mi);s.insert(k);
        if(!h[k])l[k]=r[k]=i,h[k]=1;
        else r[k]=i;mx=max(mx,k);
    }
    for(i=1;i<=m;i++){
        if(!h[i])continue;
        if(l[i]<las)break;
        R[++cnt]=r[i];
        las=r[i];it=s.find(i);
    }
    int p=cnt;las=1e6;
    for(i=m;i>=1;i--){
        if(!h[i]){
            if(p){
                add(i);
                if(las==1e6&&s.size()==cnt)ans+=i-mx;
            }
            else ans+=mi;
            continue;
        }
        if(p)add(i);
        else ans+=mi;
        if(r[i]>las)break;
        while(p&&l[i]<=R[p])p--,it--;
        las=l[i];
    }
    cout<<ans;
}

大佬,您这篇是不是O(n2logn)O(n^2\text{log}n)

import java.util.*;
import java.lang.*;

public class Solution{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] x = new int[n];

        for(int i = 0;i < n;i++){
            x[i] = sc.nextInt();
        }

        int l = 0,r = m;
        int ans = 0;
        int max = -1;
        int i = 0;
        while(r >= 1){

            i = 0;
            int count = 0;
            max = -1;
            for(;i < n;i++){
                if(x[i] > r){
                    if(x[i] < max){
                        break;
                    }
                    max = x[i];
                }
            }

            if(i < n){
                break;
            }

            int low = 1,high = r+1;

            while(low <= high){
                int mid = (low + high)/2;
                max = -1;
                i = 0;
                for(;i < n;i++){
                    if(x[i] > r || x[i] < mid){
                        if(x[i] < max){
                            break;
                        }
                        max = x[i];
                    }
                }

                if(i == n){
                    count = mid;
                    low = mid + 1;
                }else{
                    high = mid - 1;
                }
            }

            ans += count;

            r--;
        }

        System.out.println(ans);
    }

}
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
void solve() {
    int n, m; cin >> n >> m;
    vector<int> pre(m + 2), suf(m + 2), l(m + 1), r(m + 1), a(n + 1);
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        r[a[i]] = max(r[a[i]], i);
        if(!l[a[i]]) l[a[i]] = i;
    }
    //prefix
    int lastpre = -1, lastsuf = -1;
    for(int i=1;i<=m;i++) {
        if(!l[i]) {
            pre[i] = pre[i - 1];
            continue;
        }
        if(l[i] > pre[i - 1]) {
            pre[i] = r[i];
        } else {
            pre[i] = -1;
            lastpre = i - 1;
            break;
        }
    }
    suf[m + 1] = 1000000;
    vector<pair<int, int>> s;
    for(int i=m;i>=1;i--) {
        if(!r[i]) {
            suf[i] = suf[i + 1];
            continue;
        }
        if(r[i] < suf[i + 1]) {
            suf[i] = l[i];
        } else {
            suf[i] = -1;
            lastsuf = i + 1;
            break;
        }
    }
    if(lastsuf == lastpre && lastsuf == -1) {
        cout << m * (m - 1) / 2 + m;
        return;
    }
    for(int i=m+1;i>=lastsuf;i--) {
        int lastl = lower_bound(pre.begin(), pre.begin() + lastpre + 1, suf[i]) - pre.begin();
        int lastr = i - 1;
        s.emplace_back(lastr, lastl); //reversed!!!!!!!!
    }
    int cur = 0, ans = 0;
    sort(s.begin(), s.end());
    int iter = 0;
    for(int i=1;i<=m;i++) {
        while(s[iter].first == i) {
            cur = max(cur, s[iter].second);
            iter++;
        }
        ans += cur;
    }
    cout << ans;
}
signed main() {
    //fastio;
    int t = 1;
    while(t--) solve();
    return 0;
}

思路很简单,但是预期结果好像有点问题?