글 읽기 - 어떤 반례가 있을까요??

milkclouds 4년 전 0

부채꼴들을 구분하는 선을 동시에 다 돌리다보면, 점을 문제의 조건에 의해 동시에 여러개가 아니라 하나씩만 따로 따로 다른 부채꼴로 옮길 수 있겠다는 생각을 했고

하나의 부채꼴의 각도만큼만 옮기면 원래의 도형과 똑같아지니 더 옮길 필요 없다는 판단 하에 부채꼴들을 구분하는 선들과 이루는 각도가 작은 점들부터 처리하며 추가적으로 삽입하지는 않았습니다.

arr[i] 는 i번째 부채꼴에 존재하는 점의 개수이고

arr2[k]는 k==arr[i]인 i들의 개수입니다. arr2를 이용해서 arr[i]의 최댓값/최솟값을 가져오려고 했습니다.

어디가 틀린 건지 감이 안 와서 질문 게시판에 올립니다...

# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<c;a++)
#define rep2(a,b,c) for(ll a=b;a>c;a--)
#define pb push_back
#define x first
#define y second
#define all(x) x.begin(), x.end()
using namespace std;
using ll=long long;
using ti=tuple<ll,ll,ll>;
using pi=pair<int,int>;
using pdi = pair<double, int>;
const int MAX = 1e4 + 5;

int N, K, arr[1003], arr2[MAX], k, M, m = 1e9, ans = 1e9;
double A[MAX];
priority_queue<pdi> pq;
void update(int k){
	M = max(M, k); m = min(m, k);
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> N >> K;
	rep(i, 0, N) cin >> A[i];
	rep(i, 0, N) {
		k = (int)(A[i] * K / 360);
		assert(0 <= k && k < K);
		arr[k]++;
		pq.push({A[i] - (1 + k) * 360 / K, k});
	}
	rep(i, 0, K) arr2[arr[i]]++;
	rep(i, 0, K) update(arr[i]);
	ans = M - m;
	while(!pq.empty()){
		k = pq.top().y; pq.pop();
		if(arr2[arr[k]] == 1 && arr[k] == M) M--;
		if(arr2[arr[(k + 1) % K]] == 1 && arr[(k + 1) % K] == m) m++;
		arr2[arr[k]--]--; arr2[arr[(k + 1) % K]++]--;
		if(arr2[arr[k]] == 0) m = min(m, arr[k]);
		if(arr2[arr[(k + 1) % K]] == 0) M = max(M, arr[(k + 1) % K]);
		arr2[arr[k]]++;	arr2[arr[(k + 1) % K]]++;
		ans = min(ans, M - m);
	}
	cout << ans << endl;
}

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

문제

문제

출처

ICPC

어떤 반례가 있을까요??

milkclouds 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말