글 읽기 - 펜윅트리로는 풀수 없을까요?

stlee 3년 전 0

g 번 게이트에 오려 할 때, g이하의 게이트에 도킹되어 있는 비행기의 수가 g와 같으면

더이상 도킹할 수 없다고 판단하여 종료하는 방법으로 펜윅트리로 풀어보려 하는데요

계속 틀렸다고 하네요.

어디가 문제인 걸까요?

(펜윅 트리의 i번 값 : i번 이하의 게이트에 도킹된 총 비행기 수)

#include <bits/stdc++.h>
using namespace std;
struct Fenwick {
	vector<int> tree;
	Fenwick(int N) {
		tree.resize(N+1,0);
	}
	void add(int p, int v) {
		while(p<tree.size()) {
			tree[p] += v;
			p += p&-p;
		}
	}
	int sum(int p) {
		int ret=0;
		while(p >0) {
			ret+=tree[p];
			p-=p&-p;
		}
		return ret;
	}
};
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int G, P;
	cin>>G>>P;
	Fenwick fw(G);
	int ans=0;
	while(P--){
		int p; cin>>p;
		if(fw.sum(p) == p) break;
		fw.add(p, 1);
		ans++;
	}
	cout<<ans<<"\n";
}

djm03178 3년 전 0

반례입니다.

3
3
2
2
1

정답: 2
출력: 3

stlee 3년 전 0

감사합니다 ㅜㅜ

asdsa2134 3년 전 0

혹시 펜윅으로 풀이 성공하셨나요?

heeda0528 3년 전 4

훗날 세그/펜윅으로 해결하려 하시는 분들을 위해 반례를 하나 더 남깁니다.

많은 시간 고민해봤지만 그냥 유니온파인드 쓰는게 속 편할 것 같습니다 ㅠ

adxx 3년 전 1

저도 비슷하게 1~i 구간에서 도킹 가능한 공항의 수를 세그트리에 저장해서 풀어봤는데 정신건강에 매우 해롭습니다(AC 못받음😡)

neogate 2년 전 0

늦었지만 저 같은 경우에는 segtree에 도킹할 수 있는 게이트의 최대 값을 저장하는 식으로 풀었습니다.

그래야 비행기들이 들어갈 수 있는 게이트 중에서 가장 큰 위치로 들어감으로써 최대한 많은 비행기들을 넣을 수 있으니까요.

구간의 최댓값은 게이트번호가 i일때 [0,i]에서만 구해주면 되고 요 구간에서 사용할 수 있는 게이트가 없다면 끝내는 식으로 풀었습니다.

다만 주의하실점은 게이트를 이용하신 후에는 사용 처리 (-1 등으로)를 확실히 해주셔야합니다.

segtree를 타고올라가면서 최대값이 이미 사용한 게이트인 것들을 이미 쓴 것으로 바꿔주는 과정이 추가적으로 필요합니다.

tiolove 2년 전 0

저도 SegTree를 이용해서 풀었어요....

댓글을 작성하려면 로그인해야 합니다.