AT_arc179_a.[ARC179A] Partition
普及-
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
给定你整数 N 和 K。
定义长度为 N 的整数序列 X=(X1,X2,…,XN) 的前缀和为长度为 N+1 的序列 Y=(Y0,Y1,…,YN) 满足:
-
Y0=0
-
Yi=j=1∑iXj(i=1,2,…,N)
如果一个长度为 N 的整数序列 X=(X1,X2,…,XN) 满足以下条件,那么它被成为好的序列:
- 在 X 的前缀和中,任何小于 K 的值都出现在任何不小于 K 的值之前。
- 形式化的说,对于 X 的前缀和 Y,对于任意整数对 (i,j) 其中 0≤i,j≤N,如果 Yi<K 且 Yj≥K 那么 i<j。
给你一个长度为 N 的整数序列 A=(A1,A2,…,AN)。判断是否能够通过重排 A 中的元素使 A 变成一个好的序列。如果可以,输出重排后的结果。
输入格式
第一行,输入两个整数 N,K。
第二行,输入 N 个整数,表示数列 A。
输出格式
如果能够通过重排 A 使得 A 变成一个好的序列,那么:
第一行,输出 Yes。
第二行,输出 N 个整数,表示重排过后的序列 A。
如果有多个满足条件的重排后的序列,输出任意一个都会被视为是正确的。
如果无法通过重排 A 使得 A 变成一个好的序列,输出 No。
样例 1 解释
如果将 A 重排为 (−3,−1,2,4),那么 A 的前缀和 Y 为 (0,−3,−4,−2,2)。在 Y 中任何小于 1 的值都会出现在任何不小于 1 的值之前。
输入输出样例
输入#1
4 1 -1 2 -3 4
输出#1
Yes -3 -1 2 4
输入#2
4 -1 1 -2 3 -4
输出#2
No
输入#3
10 1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
输出#3
Yes -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
说明/提示
- 1≤N≤2×105;
- −109≤K≤109;
- −109≤Ai≤109;
- 所有输入都是整数。
输入解题思路,AI测评打分。不知道怎么写?