CF1492B Card Deck 题解
2024-09-06 02:17:46
Content
有 \(n\) 张纸牌组成的一个牌堆,每张纸牌都有一个价值 \(p_1,p_2,\dots,p_n\)。每次选出最顶上的几个牌放到另外一个一开始为空的牌堆里面。定义一个牌堆的总值为 \(\sum\limits_{i=1}^nn^{n-i} \cdot p_i\)。请构造出一个可能的最终的牌堆,使得这个牌堆的总值最大。
数据范围:\(t\) 组数据,\(t\in[1,10^3]\),\(1\leqslant p_i\leqslant n\leqslant 10^5\)。
Solution
我们不难想到,需要尽可能将 \(p_i\) 大的牌放到前面去,因此我们想到这样一个贪心算法:将前 \(1\sim n\) 个数的最大值所在位置记为 \(maxi_i\)(\(maxi_i\) 可以通过边读入边记录,详见代码),然后从牌顶开始,每次将 \(maxi_i\) 相等的牌按照原来的顺序放入新的牌堆,这样可以保证将 \(p_i\) 大的牌放在前面而又符合要求。
Code
int n, p[100007], maxi[100007], ans[100007], cnt;
int main() {
MT {
memset(ans, 0, sizeof(ans));
memset(maxi, 0, sizeof(maxi));
n = Rint, cnt = 0;
F(i, 1, n) {
p[i] = Rint;
if(p[i] > p[maxi[i - 1]]) maxi[i] = i, ans[++cnt] = i;
else maxi[i] = maxi[i - 1];
}
ans[++cnt] = n + 1;
R(i, cnt, 1) F(j, ans[i], ans[i + 1] - 1) printf("%d ", p[j]);
puts("");
}
return 0;
}
最新文章
- JS写随机数
- android 5.0以下版本使用atof报错解决
- HttpURLConnection用法详解
- android机型排行榜(201509)
- 配置个舒心的 Java 开发环境
- Main函数参数argc,argv说明
- UVa 1609 (博弈) Foul Play
- html JS打印添加水印图片
- 平衡树初阶——AVL平衡二叉查找树+三大平衡树(Treap + Splay + SBT)模板【超详解】
- tar命令(转)
- python:解析js中常见的 不带引号的key的 json
- Servlet CDI Example Analysis
- Spring-boot集成RabbitMQ踩过的坑
- innerHTML的使用
- java框架之SpringBoot(15)-安全及整合SpringSecurity
- jQuery-1.样式篇---选择器
- 爬虫:输入网页之后爬取当前页面的图片和背景图片,最后打包成exe
- Salesforce数据安全简介
- OneNET麒麟座应用开发之一:初识OneNET麒麟座
- 『MXNet』第四弹_Gluon自定义层