CF1427A Avoiding Zero 题解
2024-09-03 10:30:27
Content
请将一个长度为 \(n\) 的数列 \(A\) 重新排序,使得这个数列所有的前缀和 \(\neq 0\),或者证明没有这样的方案。
数据范围:\(t\) 组数据,\(1\leqslant t\leqslant 1000\),\(1\leqslant n\leqslant 50\),\(-50\leqslant a_i\leqslant A_i\leqslant 50\)。
Solution
不难发现,当且仅当所有数的和都为 \(0\) 的时候不存在满足题目要求的方案。
否则,将所有的正整数放进一起,将所有的负整数放在一起,然后分类讨论:
- 如果所有正整数的和大于所有负整数的和的绝对值,那么我们就考虑先把所有的正整数放在前面,再把所有的负整数放在后面,这样可以保证前缀和不为 \(0\)。
- 否则,我们先把所有的负整数放在前面,再把所有的正整数放在后面。
至于如果存在 \(0\),那就放在在所有的非零数后面就行了。
想法略显复杂,但是实现起来也是不难的,对吧?
Code
int n, a[57], sum, sump, sumn, po[57], ne[57];
int main() {
MT {
n = Rint, sum = sump = sumn = 0;
F(int, i, 0, n) po[i] = ne[i] = 0;
F(int, i, 1, n) sum += (a[i] = Rint), sump += a[i] * (a[i] > 0), sumn += (-a[i]) * (a[i] < 0);
if(!sum) {NO; continue;}
YES;
F(int, i, 1, n) if(a[i] > 0) po[++po[0]] = a[i]; else if(a[i] < 0) ne[++ne[0]] = a[i];
if(sump > sumn) {F(int, i, 1, po[0]) print_space(po[i]); F(int, i, 1, ne[0]) print_space(ne[i]); F(int, i, 1, n - po[0] - ne[0]) printf("0 ");}
else {F(int, i, 1, ne[0]) print_space(ne[i]); F(int, i, 1, po[0]) print_space(po[i]); F(int, i, 1, n - po[0] - ne[0]) printf("0 ");}
puts("");
}
return 0;
}
最新文章
- github入门到上传本地项目
- Quartus II中的Waring(转)
- SQL优化技巧--远程连接对象引起的CTE性能问题
- 【资源】mp3的外链资源
- 关于AS3获取当前URL和浏览器信息
- 添加hive默认配置hiverc
- Linux命令-cp
- 【http】生命周期和http管道技术 整理中
- bzoj1930
- nutch fetcher.server.delay
- 高放的c++学习笔记之模板与泛型编程
- 深入体会__cdecl与__stdcall
- CentOS 6.X x64 编译安装 Countly
- 51nod 1130 N的阶乘的长度(斯特林近似)
- 关于ruby gem无法连接到rubygems.org的解决方案
- Unity Bolt插件 基本使用
- Openflow协议详解
- [原创]K8PackWebShell ASPX整站打包工具
- php函数:解决数组转对象时数组内中文乱码问题
- 三维计算机视觉 —— 中层次视觉 —— RCNN Family