그리디문제이다
찍었는데 아직도 왜 맞는지 증명이 어렵다
그래도 생각을 적어보려고한다..
1 3 7 크기가 있다고 한다면
1 또는 3을 자르는 것은 무조건 손해다.
최대조각크기와 최소조각크기 차이가 더 벌어질 수 밖에 없기 때문이다
그래서 우선순위큐로 가장 큰 원소만 관리했다.
다음은 조각을 자를 때 5:5로 자를건지
1:9로 자를건지.. 1.9832:8.0168 비율로 자를건지.. 선택을 해야한다.
만약 칼질을 1번만 한다고하면
1:9 또는 2:8 등등 으로 자르는 것보다
5:5로 자르는게 안정적?이다..
만약 조각이 1 과 3이 있다고 가정하면
1, 1.5, 1.5가 돼서 기존의 최소인 1과 최대한 가까워지고
만약 조각이 3과 5가 있다고 가정하면
2.5, 2.5, 3 이 돼서
새로운 최대인 3과 최대한 가까워 지기때문이다
다음은 처음에 주어진 조각에 칼질을 2번 이상 할 때인데
위와 같은 생각으로 칼질을 2번할 때는 3등분으로
3번할 때는 4등분으로 ...
하는게 최적임을 대강 알 수 있었다.
마지막으로 우선순위 큐와 관련된 내용인데
m(최대 칼질 횟수)를 돌면서 pq의 top에 있는
조각만 꺼내와 칼질 횟수+1을 해주었다
m을 돌면서 pq에 있는 정보를 통해
최솟값(ans)을 갱신해줄 때마다
최대,최소의 cnt의 합은 m을 넘을 수 없다
이유는 당연하게도 m이 한번 감소할 때마다
pq의 top을 한번만 꺼내와서 cnt+1을 해주기 때문..
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int n;int m;vector<double> v;
struct aa{
double num;
int idx,cnt;
bool operator <(const aa& a)const{
return num<a.num;
}
};
priority_queue<aa> pq;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;v.resize(n);
double min_value = 1e9;
for(int i=0;i<n;i++){
cin>>v[i];
min_value=min(min_value,v[i]);
pq.push({v[i],i,1});
}
double ans = pq.top().num-min_value;
cin>>m;
while(m--){
aa a = pq.top();pq.pop();
a.num = v[a.idx]/++a.cnt;
pq.push(a);
min_value=min(min_value,a.num);
ans = min(ans,pq.top().num-min_value);
}
cout<<fixed;
cout.precision(16);
cout<<ans<<"\n";
}