UVA 501 - Black Box (이분 + 트 리 배열 + 이산 화)
사고: 이 문 제 는 구간 k 가 작 지만 복잡 한 데이터 구 조 를 사용 할 필요 가 없습니다. 우 리 는 나무 모양 의 배열 로 만 유지 하면 됩 니 다. 값 을 나무 모양 의 배열 로 표시 하기 때 문 입 니 다. 그러면 이것 은 천연 적 인 단조 로 운 구간 입 니 다. 2 분 으로 찾 으 면 됩 니 다. 또 이산 화 를 해 야 한다.
자세 한 참조 코드:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <bitset>
#include <cstdlib>
#include <cmath>
#include <set>
#include <list>
#include <deque>
#include <map>
#include <queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 30000 + 10;
int T,n,m,bit[maxn],id[maxn],a[maxn],b[maxn];
int sum(int x) {
int ans = 0;
while(x > 0) {
ans += bit[x];
x -= x & -x;
}
return ans;
}
void add(int x, int d) {
while(x <= n) {
bit[x] += d;
x += x & -x;
}
}
int main() {
scanf("%d",&T);
while(T--) {
int cnt = 0;
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) {
scanf("%d",&a[i]);
id[cnt++] = a[i];
}
//
sort(id, id+cnt);
cnt = unique(id, id+cnt) - id;
for(int j = 1; j <= m; j++) scanf("%d",&b[j]);
//
memset(bit, 0, sizeof(bit));
int cur = 0;
for(int i = 1; i <= m; i++) {
// id
if(b[i] > cur) {
for(int j = cur+1; j <= b[i]; j++) {
int v = lower_bound(id, id+cnt, a[j]) - id + 1;
add(v, 1);
}
cur = b[i];
}
int l = 1, r = cnt;
while(r > l) {
int mid = (l + r) >> 1;
int cur = sum(mid);
if(cur >= i) r = mid;
else l = mid + 1;
}
printf("%d
",id[l-1]);
}
if(T) printf("
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.