社区讨论

sort+二分TLE了一半50分

P9497「RiOI-2」weight参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mhjdosvm
此快照首次捕获于
2025/11/04 00:52
4 个月前
此快照最后确认于
2025/11/04 00:52
4 个月前
查看原帖
sort排序+二分TLE了一半只得了50分,和我的暴力解得的分居然一样:(,求助大佬!!!!!!!!
CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1e3 + 10;
int n,q;
int arr[MAXN][MAXN];

// int cmp(int a, int b) {
//     if (a > b) return a;
//     return b;
//
// } //废弃
int v; //询问
int ans = 0; //符合数
int find(int x) {//二分,每一行二分查找最后一个符合要求的数的下标
    int l = 0, r = n + 1;
    while (l + 1 != r) {
        int mid = l + (r - l) / 2;
        if (arr[x][mid] >= v) {
            l = mid;
        }
        else {
            r = mid;
        }

    }
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n>>q;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            cin>>arr[i][j];
        }

    }
    for(int i=1;i<=n;i++) {
        sort(arr[i] + 1,arr[i] + n + 1,greater<int>());

    }
    // for (int i=1;i<=n;i++) {
    //     for (int j=1;j<=n;j++) {
    //         cout<<arr[i][j]<<" ";
    //     }
    //     cout<<endl;
    // } //输出矩阵

    // for(int i=1;i<=q;i++) {
    //     int v;
    //     int ans = 0;
    //     cin>>v;
    //     for(int j=1;j<=n;j++) {
    //         for(int k=1;k<=n;k++) {
    //             if (arr[j][k] >= v) { ans++;}
    //             else { break;}
    //         }
    //     }//遍历矩阵计数符合要求答案数量(暴力解)
    //     if(ans>=n) {cout<<n<<'\n';}
    //     else cout<<ans<<'\n';
    // }
    for(int i=1;i<=q;i++) {
        ans = 0; //ans归零
        cin>>v;
        for(int j=1;j<=n;j++) {
            ans += find(j);
        }
        if(ans>=n) {cout<<n<<'\n';}
        else cout<<ans<<'\n';
    }


    return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...