[JOI 2015 Final]舞会
题目描述
IOI 王国为了庆祝 JOI 公主的生日,举行了舞会。 预定有 N 位贵族要参加舞会。 N 是奇数。将贵族们从 \(1\) 到 \(N\) 编号。每个贵族有一个由整数表示的舞蹈熟练度 。贵族 \(i\) (\(1 \leq i \leq N\)) 舞蹈熟练度为 \(D_i\)。 舞会中,含 JOI 公主在内的 \(N+1\) 人两两一组跳舞。 IOI 王国遵循老手帮新手的传统,按以下方法决定跳舞的分组。
- 开始时, \(N\) 个贵族排成一列。
- 直到队列中只剩下一个贵族为止,不断进行以下操作。
- 调查最前面 \(3\) 个贵族的舞蹈熟练度。
- 这 \(3\) 个人中舞蹈熟练度最大的贵族称为 \(A\) 。如果存在多个人,从中选出序号最小的称为 \(A\) 。
- 这 \(3\) 个人中舞蹈熟练度最小的贵族称为 \(B\) 。如果存在多个人,从中选出序号最大的称为 \(B\) 。
- \(A\) 和 \(B\) 离开队列并组成一组。
- 这三人中没有被选择的一个人移动到队列最后。
- 最后剩下的一个人和 JOI 公主一组。
从第 \(1\) 个贵族到第 \(M\)(\(1 \leq M \leq N-2\)) 个贵族的 \(M\) 个贵族已经决定了自己开始时排在队列的第几个。剩下的 \(N-M\) 个贵族的排列方式可以由国王自由决定。
因为 JOI 公主才刚开始学跳舞,国王想知道和 JOI 公主组队的贵族的舞蹈熟练度的最大值。
任务
给出每个贵族的舞蹈熟练度,和 \(M\) 个贵族开始时在队列中的位置。请编写程序求出和 JOI 公主一组的贵族的舞蹈熟练度的最大值。
输入格式
第一行为两个以空格分开的整数 \(N\),\(M\) 。分别表示舞会有 \(N\) 个贵族参加,已经决定排列位置的贵族有 \(M\) 人。
接下来 \(M\) 行中,第 \(i\) 行 (\(1\leq i \leq M\)) 为两个以空格分开的整数 \(D_i,P_i\) 。分别表示第 \(i\) 个贵族的舞蹈熟练度为 \(D_i\)。贵族 i 开始时排在队列的第 \(P_i\) 位。
接下来 N-M 行中,第 \(i\) 行 (\(1\leq i \leq N-M\)) 为一个整数 \(D_{i+M}\)。表示贵族 \((i+M)\) 的舞蹈的熟练度为 \(D_{i+M}\)。
输出格式
输出一行:表示和 JOI 公主组队的贵族的舞蹈熟练度的最大值。
solution
二分答案,但问题在于如何判断是否存在一种排列方式,使得我们能得到这个答案
我们可以发现这个淘汰的过程可以表示为一棵三叉树,那么树根的值就是答案
假设现在二分的答案为\(k\),设值大于等于\(k\)的点为黑点,小于\(k\)的点为白点
不难发现,当且仅当\(x\)的三个儿子中存在两个及以上黑点时,点\(x\)为黑点
所以我们考虑用树形DP,判断答案的合法性
设\(f_x\)表示要让\(x\)点为黑点,最少需要让多少个点为黑点(即最少放多少个\(≥k\)的点)
对于一个位置固定的点,其权值为\(a_i\),其确定的位置为\(b_i\),位置\(b_i\)对应的叶子节点为\(x\):
-
若\(a_i ≥ k\),则\(f_x=0\)
-
否则\(f_x=+∞\)
剩下的叶子节点dp值都为1
表示只需要将ta自己变为黑色即可
转移就是从儿子较小的两个转移即可
复杂度\(O(nlogn)\),足以通过此题
code
void build(){//模拟题目中淘汰过程,建树
queue<ll> q;
for(ll i=1;i<=n;i++){
q.push(i);
}
ll tot=n;//节点个数
while(!q.empty()){
ll x=++tot;//选出来的
if(q.size()==3) rt=x;//只剩下3个节点了
for(ll i=1;i<=3;i++){
add(x,q.front());
q.pop();
}
q.push(x);
if(x==rt) return ;
}
}
void dfs(ll k){
if(k<=n) return ;//叶子节点
ll mx=0;
for(ll i=hd[k];i;i=a[i].nxt){
ll y=a[i].to;
dfs(y);
dp[k]+=dp[y];
mx=max(mx,dp[y]);
}
dp[k]-=mx;//选出较小的两个=总和-最大的
}
bool check(ll x){
memset(dp,0,sizeof dp);
for(ll i=1;i<=n;i++){
dp[i]=1;
}
for(ll i=1;i<=m;i++){
if(d[i]>=x) dp[p[i]]=0;
else dp[p[i]]=INF;
}
ll sum=0;
for(ll i=m+1;i<=n;i++){
if(d[i]>=x) sum++;
}
dfs(rt);
return dp[rt]<=sum;//判断最终选出来的点若要符合≥x需要放的自由黑点是否足够
}
int main(){
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=m;i++){
scanf("%lld%lld",&d[i],&p[i]);
}
for(ll i=m+1;i<=n;i++){
scanf("%lld",&d[i]);
}
for(ll i=1;i<=n;i++){
v[i]=d[i];
}
sort(v+1,v+1+n);//排序,便于二分答案
//cout<<"---\n";
ll sz=unique(v+1,v+1+n)-v-1;//去重
build();
ll l=1,r=sz,ans;
while(l<=r){
ll mid=(l+r)>>1;
if(check(v[mid])){
l=mid+1;
ans=mid;
}else{
r=mid-1;
}
}
printf("%lld",v[ans]);
return 0;
}
完结撒花❀
★,°:.☆( ̄▽ ̄)/$:.°★ 。
标签:舞会,舞蹈,leq,贵族,2015,JOI,Final,熟练度 From: https://www.cnblogs.com/Aurora1217/p/16647746.html