[luogu]P4364[九省联考2018]IIIDX（贪心）

作者：zvan | 来源：互联网 | 2023-08-30 11:04

P4364 [九省联考2018]IIIDX 题目背景 Osu 听过没&＃xff1f;那是Konano 最喜欢的一款音乐游戏&＃xff0c;而他的梦想就是有一天自己也能做个独特酷炫的音乐游戏。现在&＃

P4364 [九省联考2018]IIIDX

题目背景

Osu 听过没&＃xff1f;那是Konano 最喜欢的一款音乐游戏&＃xff0c;而他的梦想就是有一天自己也能做个独特酷炫的音乐游戏。现在&＃xff0c;他在世界知名游戏公司KONMAI 内工作&＃xff0c;离他的梦想也越来越近了。

这款音乐游戏内一般都包含了许多歌曲&＃xff0c;歌曲越多&＃xff0c;玩家越不易玩腻。同时&＃xff0c;为了使玩家在游戏上氪更多的金钱花更多的时间&＃xff0c;游戏一开始一般都不会将所有曲目公开&＃xff0c;有些曲目你需要通关某首特定歌曲才会解锁&＃xff0c;而且越晚解锁的曲目难度越高。

题目描述

这一天&＃xff0c;Konano 接到了一个任务&＃xff0c;他需要给正在制作中的游戏《IIIDX》安排曲目的解锁顺序。游戏内共有n 首曲目&＃xff0c;每首曲目都会有一个难度d&＃xff0c;游戏内第i 首曲目会在玩家Pass 第\(\lfloor \frac{i}{k} \rfloor\) 首曲目后解锁&＃xff08;\(\lfloor x \rfloor\) 为下取整符号&＃xff09;若\(\lfloor \frac{i}{k} \rfloor &＃61; 0\)&＃xff0c;则说明这首曲目无需解锁

举个例子&＃xff1a;当k &＃61; 2 时&＃xff0c;第1 首曲目是无需解锁的&＃xff08;\(\lfloor \frac{1}{2} \rfloor &＃61; 0\)&＃xff09;&＃xff0c;第7 首曲目需要玩家Pass 第\(\lfloor \frac{7}{2} \rfloor &＃61; 3\) 首曲目才会被解锁。

Konano 的工作&＃xff0c;便是安排这些曲目的顺序&＃xff0c;使得每次解锁出的曲子的难度不低于作为条件需要玩家通关的曲子的难度&＃xff0c;即使得确定顺序后的曲目的难度对于每个i 满足

\(d_i \geq d_{\lfloor \frac{i}{k} \rfloor}\)

当然这难不倒曾经在信息学竞赛摸鱼许久的Konano。那假如是你&＃xff0c;你会怎么解决这份任务呢&＃xff1f;

输入输出格式

输入格式&＃xff1a;

第1 行1 个正整数n 和1 个小数k&＃xff0c;n 表示曲目数量&＃xff0c;k 其含义如题所示。

第2 行n 个用空格隔开的正整数d&＃xff0c;表示这n 首曲目的难度。

输出格式&＃xff1a;

输出到文件iiidx.out 中。

输出1 行n 个整数&＃xff0c;按顺序输出安排完曲目顺序后第i 首曲目的难度。

若有多解&＃xff0c;则输出d1 最大的&＃xff1b;若仍有多解&＃xff0c;则输出d2最大的&＃xff0c;以此类推。

输入输出样例

输入样例#1&＃xff1a; 复制

4 2.0
114 514 1919 810

输出样例#1&＃xff1a; 复制

114 810 514 1919

说明

题解

做个人不好吗。。

本题有一个55分的贪心&＃xff0c;~~可以过60分~~
就是直接按题意暴力建树然后贪心&＃xff0c;能赋大值就赋大值。
树的边就是按\(\lfloor \frac{i}{k} \rfloor\)来的。

事实上这个贪心是不能解决多个\(d_i\)相同的。
如

input 4 2.0 1 1 1 2 output 1 1 2 1 错误答案 1 1 1 2

即在建树过程中&＃xff0c;&＃xff08;图片来自NaVi_Awson&＃xff09;

当2节点和4节点可以取相同值&＃xff0c;且3独立时&＃xff0c;我们应该是优先&＃xff0c;2,4为1&＃xff0c;3为2的&＃xff0c;但是贪心一定会把2赋值给4节点。

我们维护一个数组\(f[i]\),表示\(i\)节点之前还有剩余的点数。
从大到小排序&＃xff0c;然后我们找优先靠左的满足\(f[i]>&＃61;size[x]\)的数字。
\(size[x]\)表示答案序列第\(x\)位的子树大小。
然后维护一个\(nxt[]\)数组&＃xff0c;表示相同的数值时优先选靠右的。
然后第\(i\)到\(n\)位的\(f[]-size[x]\);
这样可以解决掉那个重复的带来的影响。
两个循环暴力找和减去是\(O(n^2)\)
转移到线段树上就可以了\(O(nlogn)\)

我之前一直不明白为什么如果当前点有父亲&＃xff0c;要重新加上父亲的预留值。

Code

#include #include #include #include #include using namespace std; const int N&＃61;1e6&＃43;5; int sum[N<<2],lazy[N<<2]; int a[N],n,ans[N],size[N],fa[N],nxt[N]; double k; int read(){int x&＃61;0,w&＃61;1;char ch&＃61;getchar();while(ch>&＃39;9&＃39;||ch<&＃39;0&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)w&＃61;-1;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;)x&＃61;x*10&＃43;ch-&＃39;0&＃39;,ch&＃61;getchar();return x*w; }void build(int root,int left,int right){int mid&＃61;(left&＃43;right)>>1;if(left&＃61;&＃61;right){sum[root]&＃61;left;return ;}build(root<<1,left,mid);build(root<<1|1,mid&＃43;1,right);sum[root]&＃61;min(sum[root<<1],sum[root<<1|1]); }void push(int root,int left,int right){sum[root<<1]&＃43;&＃61;lazy[root];sum[root<<1|1]&＃43;&＃61;lazy[root];lazy[root<<1]&＃43;&＃61;lazy[root];lazy[root<<1|1]&＃43;&＃61;lazy[root];lazy[root]&＃61;0; }void update(int root,int left,int right,int l,int r,int v){if(left>r||right&＃61;l&&right<&＃61;r){sum[root]&＃43;&＃61;v;lazy[root]&＃43;&＃61;v;return ;}int mid&＃61;(left&＃43;right)>>1;if(mid>&＃61;l) update(root<<1,left,mid,l,r,v);if(mid}int query(int root,int left,int right,int k){if(left&＃61;&＃61;right){return sum[root]>&＃61;k?left:left&＃43;1;}int mid&＃61;(left&＃43;right)>>1;if(lazy[root])push(root,left,right);if(sum[root<<1|1]>&＃61;k) return query(root<<1,left,mid,k);else return query(root<<1|1,mid&＃43;1,right,k);}bool cmp(int a,int b){return a>b;}int main(){n&＃61;read();cin>>k;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)a[i]&＃61;read();sort(a&＃43;1,a&＃43;n&＃43;1,cmp);for(int i&＃61;n;i>&＃61;1;i--){nxt[i]&＃61;i;fa[i]&＃61;(1.0*i/k);size[i]&＃43;&＃43;;size[fa[i]]&＃43;&＃61;size[i];if(a[i]&＃61;&＃61;a[i&＃43;1])nxt[i]&＃61;nxt[i&＃43;1];}build(1,1,n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){if(fa[i]&&fa[i]!&＃61;fa[i-1])update(1,1,n,ans[fa[i]],n,size[fa[i]]-1);int tmp&＃61;nxt[query(1,1,n,size[i])];ans[i]&＃61;tmp;update(1,1,n,tmp,n,-size[i]);}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)cout<}

P4364 [九省联考2018]IIIDX
题目背景
Osu 听过没&＃xff1f;那是Konano 最喜欢的一款音乐游戏&＃xff0c;而他的梦想就是有一天自己也能做个独特酷炫的音乐游戏。现在&＃xff0c;他在世界知名游戏公司KONMAI 内工作&＃xff0c;离他的梦想也越来越近了。

题目描述
这一天&＃xff0c;Konano 接到了一个任务&＃xff0c;他需要给正在制作中的游戏《IIIDX》安排曲目的解锁顺序。游戏内共有n 首曲目&＃xff0c;每首曲目都会有一个难度d&＃xff0c;游戏内第i 首曲目会在玩家Pass 第\lfloor \frac{i}{k} \rfloor⌊
k
i

⌋ 首曲目后解锁&＃xff08;\lfloor x \rfloor⌊x⌋ 为下取整符号&＃xff09;若\lfloor \frac{i}{k} \rfloor &＃61; 0⌊
k
i

⌋&＃61;0&＃xff0c;则说明这首曲目无需解锁

举个例子&＃xff1a;当k &＃61; 2 时&＃xff0c;第1 首曲目是无需解锁的&＃xff08;\lfloor \frac{1}{2} \rfloor &＃61; 0⌊
2
1

⌋&＃61;0&＃xff09;&＃xff0c;第7 首曲目需要玩家Pass 第\lfloor \frac{7}{2} \rfloor &＃61; 3⌊
2
7

⌋&＃61;3 首曲目才会被解锁。

d_i \geq d_{\lfloor \frac{i}{k} \rfloor}d
i

≥d
⌊
k
i

⌋

当然这难不倒曾经在信息学竞赛摸鱼许久的Konano。那假如是你&＃xff0c;你会怎么解决这份任务呢&＃xff1f;

输入输出格式
输入格式&＃xff1a;

第1 行1 个正整数n 和1 个小数k&＃xff0c;n 表示曲目数量&＃xff0c;k 其含义如题所示。

第2 行n 个用空格隔开的正整数d&＃xff0c;表示这n 首曲目的难度。

输出格式&＃xff1a;

输出到文件iiidx.out 中。

输出1 行n 个整数&＃xff0c;按顺序输出安排完曲目顺序后第i 首曲目的难度。

若有多解&＃xff0c;则输出d1 最大的&＃xff1b;若仍有多解&＃xff0c;则输出d2最大的&＃xff0c;以此类推。

输入输出样例
输入样例#1&＃xff1a; 复制

4 2.0
114 514 1919 810

输出样例#1&＃xff1a; 复制

114 810 514 1919

说明

题解
做个人不好吗。。

本题有一个55分的贪心&＃xff0c;可以过60分
就是直接按题意暴力建树然后贪心&＃xff0c;能赋大值就赋大值。
树的边就是按\lfloor \frac{i}{k} \rfloor⌊
k
i

⌋来的。

事实上这个贪心是不能解决多个d_id
i

相同的。
如

input
4 2.0
1 1 1 2
output
1 1 2 1
错误答案
1 1 1 2
即在建树过程中&＃xff0c;&＃xff08;图片来自NaVi_Awson&＃xff09;

当2节点和4节点可以取相同值&＃xff0c;且3独立时&＃xff0c;我们应该是优先&＃xff0c;2,4为1&＃xff0c;3为2的&＃xff0c;但是贪心一定会把2赋值给4节点。

我们维护一个数组f[i]f[i],表示ii节点之前还有剩余的点数。
从大到小排序&＃xff0c;然后我们找优先靠左的满足f[i]>&＃61;size[x]f[i]>&＃61;size[x]的数字。
size[x]size[x]表示答案序列第xx位的子树大小。
然后维护一个nxt[]nxt[]数组&＃xff0c;表示相同的数值时优先选靠右的。
然后第ii到nn位的f[]-size[x]f[]−size[x];
这样可以解决掉那个重复的带来的影响。
两个循环暴力找和减去是O(n^2)O(n
2
)
转移到线段树上就可以了O(nlogn)O(nlogn)

我之前一直不明白为什么如果当前点有父亲&＃xff0c;要重新加上父亲的预留值。

Code

include

include
using namespace std;
const int N&＃61;1e6&＃43;5;
int sum[N<<2],lazy[N<<2];
int a[N],n,ans[N],size[N],fa[N],nxt[N];
double k;
int read(){
int x&＃61;0,w&＃61;1;char ch&＃61;getchar();
while(ch>&＃39;9&＃39;||ch<&＃39;0&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)w&＃61;-1;ch&＃61;getchar();}
while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;)x&＃61;x10&＃43;ch-&＃39;0&＃39;,ch&＃61;getchar();
return xw;
}

void build(int root,int left,int right){
int mid&＃61;(left&＃43;right)>>1;
if(left&＃61;&＃61;right){
sum[root]&＃61;left;return ;
}build(root<<1,left,mid);build(root<<1|1,mid&＃43;1,right);
sum[root]&＃61;min(sum[root<<1],sum[root<<1|1]);
}

void push(int root,int left,int right){
sum[root<<1]&＃43;&＃61;lazy[root];sum[root<<1|1]&＃43;&＃61;lazy[root];
lazy[root<<1]&＃43;&＃61;lazy[root];lazy[root<<1|1]&＃43;&＃61;lazy[root];
lazy[root]&＃61;0;
}

void update(int root,int left,int right,int l,int r,int v){
if(left>r||right if(lazy[root])push(root,left,right);
if(left>&＃61;l&&right<&＃61;r){
sum[root]&＃43;&＃61;v;lazy[root]&＃43;&＃61;v;
return ;
}int mid&＃61;(left&＃43;right)>>1;
if(mid>&＃61;l) update(root<<1,left,mid,l,r,v);
if(mid sum[root]&＃61;min(sum[root<<1],sum[root<<1|1]);
}

int query(int root,int left,int right,int k){
if(left&＃61;&＃61;right){
return sum[root]>&＃61;k?left:left&＃43;1;
}int mid&＃61;(left&＃43;right)>>1;
if(lazy[root])push(root,left,right);
if(sum[root<<1|1]>&＃61;k) return query(root<<1,left,mid,k);
else return query(root<<1|1,mid&＃43;1,right,k);

}

bool cmp(int a,int b){return a>b;}

int main(){
n&＃61;read();cin>>k;
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)a[i]&＃61;read();sort(a&＃43;1,a&＃43;n&＃43;1,cmp);
for(int i&＃61;n;i>&＃61;1;i--){
nxt[i]&＃61;i;fa[i]&＃61;(1.0*i/k);
size[i]&＃43;&＃43;;size[fa[i]]&＃43;&＃61;size[i];
if(a[i]&＃61;&＃61;a[i&＃43;1])nxt[i]&＃61;nxt[i&＃43;1];
}build(1,1,n);
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){
if(fa[i]&&fa[i]!&＃61;fa[i-1])update(1,1,n,ans[fa[i]],n,size[fa[i]]-1);
int tmp&＃61;nxt[query(1,1,n,size[i])];ans[i]&＃61;tmp;
update(1,1,n,tmp,n,-size[i]);
}
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)cout< return 0;
}
Markdown selection 21 bytes 2 words 0 lines Ln 1, Col 23 HTML 3224 characters 246 words 115 paragraphs

转:https://www.cnblogs.com/hhh1109/p/10667185.html

推荐阅读

ip
CF：3D City Model（小思维）问题解析和代码实现

本文通过解析CF：3D City Model问题，介绍了问题的背景和要求，并给出了相应的代码实现。该问题涉及到在一个矩形的网格上建造城市的情景，每个网格单元可以作为建筑的基础，建筑由多个立方体叠加而成。文章详细讲解了问题的解决思路，并给出了相应的代码实现供读者参考。 ... [详细]

蜡笔小新 2023-12-13 14:17:11
go
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
go
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
go
UVALive6575 Odd and Even Zeroes 数位dp+找规律

本文介绍了UVALive6575题目Odd and Even Zeroes的解法，使用了数位dp和找规律的方法。阶乘的定义和性质被介绍，并给出了一些例子。其中，部分阶乘的尾零个数为奇数，部分为偶数。 ... [详细]

蜡笔小新 2023-12-13 14:19:28
go
李逍遥寻找仙药的迷阵之旅

本文讲述了少年李逍遥为了救治婶婶的病情，前往仙灵岛寻找仙药的故事。他需要穿越一个由M×N个方格组成的迷阵，有些方格内有怪物，有些方格是安全的。李逍遥需要避开有怪物的方格，并经过最少的方格，找到仙药。在寻找的过程中，他还会遇到神秘人物。本文提供了一个迷阵样例及李逍遥找到仙药的路线。 ... [详细]

蜡笔小新 2023-12-12 13:59:33
settings
单击后为什么远程通知操作无效？ - Why remote notification action is doing nothing after clicking?

IhaveconfiguredanactionforaremotenotificationwhenitarrivestomyiOsapp.Iwanttwodiff ... [详细]

蜡笔小新 2023-12-14 15:57:44
settings
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
ip
九度OnlineJudge之1002：Grading问题的解决方法

本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程，将每个考题分配给3个独立的专家，如果他们的评分不一致，则需要请一位裁判做出最终决定。文章详细描述了评分规则，并给出了解决该问题的程序。 ... [详细]

蜡笔小新 2023-12-14 13:00:09
ip
油田地块的划分和计数方法

本文介绍了一种划分和计数油田地块的方法。根据给定的条件，通过遍历和DFS算法，将符合条件的地块标记为不符合条件的地块，并进行计数。同时，还介绍了如何判断点是否在给定范围内的方法。 ... [详细]

蜡笔小新 2023-12-14 09:18:20
go
[CF949D]Curfew 二分答案是个不错的开头，困难部分在于如何检查

本文介绍了一个题目的解法，通过二分答案来解决问题，但困难在于如何进行检查。文章提供了一种逃逸方式，通过移动最慢的宿管来锁门时跑到更居中的位置，从而使所有合格的寝室都居中。文章还提到可以分开判断两边的情况，并使用前缀和的方式来求出在任意时刻能够到达宿管即将锁门的寝室的人数。最后，文章提到可以改成O(n)的直接枚举来解决问题。 ... [详细]

蜡笔小新 2023-12-13 09:08:55
go
3.223.28周学习总结中的贪心作业收获及困惑

本文是对3.223.28周学习总结中的贪心作业进行总结，作者在解题过程中参考了他人的代码，但前提是要先理解题目并有解题思路。作者分享了自己在贪心作业中的收获，同时提到了一道让他困惑的题目，即input details部分引发的疑惑。 ... [详细]

蜡笔小新 2023-12-13 03:42:02
controller
iOS实现UITextField+Limit的字符限制方法

本文介绍了在iOS开发中使用UITextField实现字符限制的方法，包括利用代理方法和使用BNTextField-Limit库的实现策略。通过这些方法，开发者可以方便地限制UITextField的字符个数和输入规则。 ... [详细]

蜡笔小新 2023-12-12 09:50:30
object
向QTextEdit拖放文件的方法及实现步骤

本文介绍了在使用QTextEdit时如何实现拖放文件的功能，包括相关的方法和实现步骤。通过重写dragEnterEvent和dropEvent函数，并结合QMimeData和QUrl等类，可以轻松实现向QTextEdit拖放文件的功能。详细的代码实现和说明可以参考本文提供的示例代码。 ... [详细]

蜡笔小新 2023-12-14 16:06:38
object
C++省略号类型和参数个数不确定函数参数范例

本文介绍了C++中省略号类型和参数个数不确定函数参数的使用方法，并提供了一个范例。通过宏定义的方式，可以方便地处理不定参数的情况。文章中给出了具体的代码实现，并对代码进行了解释和说明。这对于需要处理不定参数的情况的程序员来说，是一个很有用的参考资料。 ... [详细]

蜡笔小新 2023-12-14 12:36:28
ip
Html5-Canvas实现简易的抽奖转盘效果

本文介绍了如何使用Html5和Canvas标签来实现简易的抽奖转盘效果，同时使用了jQueryRotate.js旋转插件。文章中给出了主要的html和css代码，并展示了实现的基本效果。 ... [详细]

蜡笔小新 2023-12-13 06:02:20

zvan

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章