[여름방학 특집 훈련 \ # 데이터 구조]
[제목 링크]: 여 기 를 클릭 하 세 요 ~ ~
[제목 부주의]
모든 사람 에 게 실력 치 랭 킹 이 있 습 니 다. 순 서 는 바로 그의 위치 입 니 다. 가장 많은 경 기 를 요구 합 니 다. 경 기 는 두 명의 동료, 한 명의 심판 을 요구 하고 심판 의 실력 을 그들 사이 에 요구 합 니 다. 그리고 위 치 는 그들 두 사람의 중간 에 있어 야 합 니 다. 이렇게 하면 한 경 기 를 구성 할 수 있 습 니 다.-- 총 몇 경 기 를 조직 할 수 있 나.
[사고]: 이 문 제 는 트 리 배열 (BIT) 을 사용 해 야 합 니 다.
BIT 는 이러한 데이터 구조 이다.
주어진 초기 값 이 0 인 수열 a1, a2...
1: 주어진 i: 계산 a1 + a2 +. ai;
2: 주어진 i 와 x: 실행 ai + = x
나무 모양 배열 을 처음 만 들 었 을 때 는 아주 오래 전 ~ ~ ~, 아직도 쓰기 에 익숙 하지 않 습 니 다. 나무 모양 배열 이 실현 할 수 있 는 기능 선분 나 무 는 기본적으로 모두 실현 할 수 있 지만, 반대로 꼭 그렇지 는 않 습 니 다. 하지만 나무 모양 배열 의 효율 이 비교적 높다 고 합 니 다. BIT 운용 번호 의 이 진 표 시 는 구간 과 매우 쉽게 대응 할 수 있 기 때 문 입 니 다.따라서 이 성질 을 이용 하여 간단 한 비트 연산 으로 실현 한다.
돌아 와 서 이 문 제 를 보 세 요. 만약 에 a [i] 가 자신 을 심판 으로 한 다음 에 왼쪽 에 몇 명 이 자신 보다 작은 지 찾 아 보 세 요. 그리고 오른쪽 에 몇 명 이 자신 보다 큰 지 찾 아 보 세 요. 그리고 두 개의 숫자 를 곱 하 는 것 은 바로 그 를 심판 으로 하 는 경기 장 수 입 니 다. 물론 반대 도 있 습 니 다. 오른쪽 이 자신 보다 작은 것 을 찾 고 왼쪽 이 자신 보다 큰 것 을 찾 아 곱 하 는 것 입 니 다.
얼마나 작 거나 큰 개 수 를 빨리 찾 으 려 면 BIT 의 역할 을 해 야 합 니 다.
정의:
LL left_low[N],left_big[N]; LL right_low[N],right_big[N];
그러면 정 답 은... res+=left_low[i]*right_big[i]+left_big[i]*right_low[i];
코드:
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
typedef long long LL;
int lowbit(int x){return x&(-x);}
LL num[N];
LL bit[N];
LL left_low[N],left_big[N];
LL right_low[N],right_big[N];
LL n;
LL sum(int i){
LL s=0;
while(i>0){
s+=bit[i];
i-=lowbit(i);
}
return s;
}
void add(int i,int x){
while(i<=N){
bit[i]+=x;
i+=lowbit(i);
}
}
int main(){
int t;scanf("%d",&t);
while(t--){
scanf("%lld",&n);
for(int i=1; i<=n; ++i){
scanf("%lld",&num[i]);
}
LL res=0;
memset(bit,0,sizeof(bit));
for(int i=1; i<=n; ++i){
add(num[i],1);
left_big[i]=sum(N)-sum(num[i]);
left_low[i]=sum(num[i]-1);
}
memset(bit,0,sizeof(bit));
for(int i=n; i>=1; --i){
add(num[i],1);
right_big[i]=sum(N)-sum(num[i]);
right_low[i]=sum(num[i]-1);
}
// left_lower[i]: i num[i]
// n-i-right_lower[i]:num[i] num[i]
// right_lower[i]: i num[i]
// i-left_lower[i]-1:num[i] num[i]
for(LL i=1; i<=n; ++i){
//res+=(left_lower[i]*(n-i-right_lower[i])+right_lower[i]*(i-left_lower[i]-1));
res+=left_low[i]*right_big[i]+left_big[i]*right_low[i];
}
printf("%lld
",res);
}
return 0;
}
HDU 1806 빈번 한 값 (이산 화 + RMQ)
[제목 링크]: 여 기 를 클릭 하 세 요 ~ ~
[제목 부주의]:
길이 가 N (N < = 100000) 인 단조 로 운 하강 서열 Si 를 정 하고, 그 다음 에 Q (Q < = 100000) 조 에 게 주어진 구간 에 가장 많은 수의 횟수 가 나타 나 는 지 물 어보 세 요.
[사고방식]: 이것 은 사 고 를 비교적 고찰 하 는 문제 입 니 다.
Q 가 매우 크기 때문에 문의 의 복잡 도 는 반드시 log (n) 가 있어 야 한다. 그러면 먼저 선분 트 리 라 는 것 을 확인한다. 이 문 제 는 제한 조건 이 있 고 모든 수 는 단 조 롭 고 증가 하지 않 는 배열 이다. 다시 말 하면 두 수가 같다 면 그들 사이 의 모든 수 는 반드시 그들 과 같다 는 것 이다.그래서 O (Q log (n)) (RMQ 를 사용 하면 O (Q) 의 알고리즘 이 생 겼 습 니 다.
모든 수 에 대해 하나의 그룹 번 호 를 설정 하면 이산 화 라 고도 할 수 있 습 니 다. 같은 수 는 같은 그룹 번 호 를 가 진 다음 에 각 수의 빈 도 를 한 배열 에 기록 하여 이런 수의 크기 를 나타 내 고 입력 에 대한 문의 [x, y] 는 그들 이 어느 그룹 에 있 는 지 직접 조회 하고 세 가지 상황 으로 나 누 어 토론 합 니 다.
1) 만약 x 와 y 가 한 그룹 에 있다 면 가장 긴 길 이 는 y - x + 1 이다.
2) 그룹 번호 가 1 차이 가 나 면 이들 의 분계 점 z (z 점 과 x 점 의 조합 번호 가 같다 고 가정) 를 찾 아 라. 그러면 답 은 Max {z - x + 1, y - z} 이다.
3) 만약 에 차이 가 1 보다 크 면 먼저 두 끝 을 자 르 고 큰 기록 을 통계 한 다음 에 중간 부분의 최대 치 와 크기 를 비교 하면 중간 부분의 최대 치 는 선분 트 리 를 사용 할 수 있다. 혹은 RMQ 구간 조회 최 값.
코드 (RMQ):
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10;
LL n,q;
LL bit[N],cnt[N];
LL num[N];
LL dpmax[N][20];///max
LL dpmin[N][20];///min
struct node ///
{
int beg,end;
}line[N];
void getline(){ /// ， ，“ ” //O(N)
memset(cnt,0,sizeof(cnt));///
int k=1;int tmp=num[1];
num[1]=1;cnt[1]=1;
line[1].beg=1;
for(int i=2; i<=n; ++i){
if(num[i]!=tmp){/// appear the new sequence
tmp=num[i];
line[k].end=i-1;
num[i]=++k;
cnt[k]++;
line[k].beg=i;
}
else{ ///tmp==num[i]
num[i]=k;
cnt[k]++;
}
}
line[k].end=n;
}
void RMQ_init(){ ///RMQ
for(int i=1; i<=n; ++i) dpmax[i][0]=cnt[i];
double limit=log(n)/log(2.0);
for(int j=1; j<=(int)limit; ++j)
for(int i=1; i+(1<<j)-1<=n; ++i){
dpmax[i][j]=max(dpmax[i][j-1],dpmax[i+(1<<(j-1))][j-1]);
// dpmin[i][j]=min(dpmin[i][j-1],dpmin[i+(1<<(j-1))][j-1]);
}
}
LL getmax(LL a,LL b){
LL k=(int)(log(b-a+1)/log(2.0));
return max(dpmax[a][k],dpmax[b-(1<<k)+1][k]);
}
LL mid_max;
int main()
{
while(scanf("%lld",&n)!=EOF&&n){
scanf("%lld",&q);
for(int i=1; i<=n; ++i) scanf("%lld",&num[i]);
getline();
RMQ_init();
while(q--){
LL a,b;
scanf("%lld%lld",&a,&b);
if(num[a]==num[b]) printf("%lld
",b-a+1);
else if(num[a]==num[b]-1){
printf("%lld
",max(line[num[a]].end-a+1,b-line[num[a]].end));
}
else{ //a,b 1
mid_max=getmax(num[a]+1,num[b]-1);//
printf("%lld
",max(mid_max,max(line[num[a]].end-a+1,b-line[num[b]].beg+1)));
}
}
} return 0;
}
POJ 2431 Expediton (욕심 + 우선 대기 열)
[제목 링크]: 여 기 를 클릭 하 세 요 ~ ~
[제목 부주의]:
트럭 한 대가 L 단위 의 거 리 를 운행 해 야 한다.처음에는 트럭 에 P 단위 의 휘발유 가 있 었 고 앞으로 1 단 위 를 달 릴 때마다 휘발유 1 단 위 를 소모 했다.도중에 차 의 휘발유 가 다 떨 어 지면 트럭 은 더 이상 갈 수 없고 결승점 에 도착 할 수 없다.도중에 모두 N 개의 주유소 가 있 는데 주유소 가 제공 하 는 유량 이 제한 되 어 있 고 트럭 의 오 일 탱크 는 무 한 히 커서 아무리 기름 을 넣 어도 문제 가 없다.각 주유소 의 종점 거리 와 제공 할 수 있 는 유량 을 제시 하고 트럭 에 출발점 에서 종점 까지 적어도 몇 번 의 기름 을 넣 어야 하 느 냐 고 물 었 다.종점 에 도착 하지 못 하면 출력 - 1.[사고방식]: N 이 비교적 크기 때문에 효율 적 인 해법 을 찾 아야 합 니 다.트럭 이 종점 으로 가 는 도중에 주유소 에서 만 기름 을 넣 을 수 있다.하지만 '주유소 i 에 도 착 했 을 때 그 이후 언제든지 비 단위 휘발 유 를 넣 을 수 있 는 권 리 를 한 번 얻 었 다' 고 생각하면 문제 해결 에 도 마찬가지다.이후 주유 가 필요 할 때 는 앞서 지나 간 주유소 에 기름 을 넣 었 다 고 생각하면 된다.주유 횟수 가 가능 한 한 적 었 으 면 좋 겠 기 때문에 연료 가 0 이 되면 다시 주유 하 는 것 이 최선 이다.욕심 에 따라 연료 가 0 일 때 가장 많은 주유 소 를 선택한다.따라서 지나 가 는 주유소 의 유량 을 우선 대기 열 로 저장 할 수 있 으 며, 주유 가 필요 할 때 대기 열 에 있 는 최대 요 소 를 꺼 내 면 된다.
#include <stdio.h>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1000005;
struct node{
int dist,val;/// the dist and the mount of oil
bool operator < (const node &a) const{
return dist<a.dist;
}
}line[N];
int n,l,p;
void solve(){
int ans=0,pos=0,tank=p;///the primary oil
priority_queue <int >val;
for(int i=0; i<=n; ++i){
int d=line[i].dist-pos; ///
while(tank<d){
if(val.empty()){
puts("-1");
return;
}
tank+=val.top();
val.pop();
ans++;
}
tank-=d;
pos=line[i].dist;
val.push(line[i].val);
}
printf("%d
",ans);
}
void init(){
scanf("%d",&n);
for(int i=0; i<n; ++i) scanf("%d %d",&line[i].dist,&line[i].val);
scanf("%d%d",&l,&p);
for(int i=0; i<n; ++i) line[i].dist=l-line[i].dist;
line[n].dist=l;line[n].val=0;
sort(line,line+n+1);
}
int main(){
init();
solve();
return 0;
}
/*
Sample Input
4
4 4
5 2
11 5
15 10
25 10
Sample Output
2
*/POJ 3253 Fence Repair 욕심 + 우선 대기 열
[제목 링크]: 여 기 를 클릭 하 세 요 ~ ~
[제목 대의]: 아주 긴 널 빤 지 를 N 조각 으로 자 르 고 자 르 려 고 하 는 길 이 는 각각 L1, L2, L3 이다. 매번 에 널 빤 지 를 자 르 는 비용 은 원래 널빤지 의 길이 의 합 이다. 예 를 들 어 길이 21 의 널 빤 지 는 5, 8, 8, 3 조각 으로 자 르 고 비용 은 21, 13 이 며 마지막 비용 은 21 + 13 = 34 로 최소 비용 을 써 야 한다.
[사고]: 널빤지 의 집합 에서 가장 짧 은 두 조각 을 꺼 내 고 길 이 를 두 개의 널빤지 와 합 친 판 자 를 집합 에 넣 으 면 되 기 때문에 우선 대기 열 로 실현 할 수 있 습 니 다.
코드:
#include <stdio.h>
#include <queue>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=20005;
typedef long long LL;
LL num[N];
LL n;
void solve(){
priority_queue <int ,vector<int >,greater<int > >val;
while(!val.empty()) val.pop();
for(int i=1; i<=n; ++i) val.push(num[i]);
LL ans=0;
while(val.size()>1){
int l1=val.top();val.pop();
int l2=val.top();val.pop();
int l3=l1+l2;ans+=(l3);
val.push(l3);
}
printf("%lld
",ans);
}
void init(){
scanf("%lld",&n);
for(int i=1; i<=n; ++i)
scanf("%lld",&num[i]);
}
int main(){
init();
solve();
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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
