社区讨论
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 条回复,欢迎继续交流。
正在加载回复...