我在解決 codechef 問題Lowest Sum時遇到了一個奇怪的問題。
有一個代碼區域來計算 sum(a[i] a[j])<X 的 pair(i,j) 的數量，想法是列舉每個 a[i]，累加小于 Xa 的數字[i] 在向量 b 中。有兩種方法可以找到向量 b 中小于 Xa[i] 的數字：
- 在）：
for(int i=0; i<K&&mid-a[i]>=b[0]; i ) {
int j=K-1;
while(j>=0 && mid-a[i]<b[j]) {
--j;
}
ans =j 1;
}
- O(登錄)
for(int i=0; i<K&&mid-a[i]>=b[0]; i ) {
auto it = upper_bound(b.begin(), b.end(), mid-a[i]);
ans = it-b.begin();
}
O(logn) 應該比 O(n) 快，但是 O(n) 可以在 2s 和 O(logn) TLE 內通過。什么原因？提前致謝。
供您參考的代碼：
#include <bits/stdc .h>
using namespace std;
using ll = long long;
int T, K, Q;
int main() {
scanf("%lld", &T);
while(T--) {
cin >> K >> Q;
vector<ll> a(K), b(K);
for(int i=0; i<K; i ) {
scanf("%lld", &a[i]);
}
for(int i=0; i<K; i ) {
scanf("%lld", &b[i]);
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
while(Q-->0) {
int qu;
scanf("%d", &qu);
ll low = a[0] b[0];
ll high = a[K-1] b[K-1];
ll ans = high;
while(low<=high) {
ll mid = (low high)/2;
int cnt = 0, j=K-1;
for(int i=0; i<K&&mid-a[i]>=b[0]; i ) {
/*
// can pass within 2 seconds
while(j>=0 && b[j]>mid-a[i]) j--;
cnt = j 1;
*/
// TLE
auto it = upper_bound(b.begin(), b.end(), mid-a[i]);
cnt = it-b.begin();
}
if(cnt>=qu) {
ans = mid;
high=mid-1;
}else {
low=mid 1;
}
}
printf("%lld\n", ans);
}
}
return 0;
}
uj5u.com熱心網友回復：
“參考代碼”j僅在i回圈外初始化一次。因此，如果取消注釋，“O(n)”版本實際上看起來像：
int j=K-1; // <----------- HERE
for(int i=0; i<K&&mid-a[i]>=b[0]; i ) {
//int j=K-1; // <----------- NOT HERE
while(j>=0 && mid-a[i]<b[j]) {
--j;
}
ans =j 1;
}
這為O(1)內部回圈提供了攤銷的運行時間，因為j在大多數情況下可以遞減K。與O(log K)TLE 版本相比。
換句話說，整個for(int i...)回圈的運行時間是O(K)在第一種情況下，而不是O(K log K)在第二種情況下。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/391632.html
下一篇：尋找有效的子串