H Bsq AK ZUCCPC
时间:2023-05-03 21:07:00
https://ac.nowcoder.com/acm/contest/9934/H
问题解释是贪婪,然后我就没用了?
AK和爆0计算范围一样,总人数-做对人数=做错的人数。
首先是最大值,比较简单,就是数组中的最小值。
然后计算最小值,这可以想象成不同种类的天气,如1-3雨,2-4雪,只有重叠的2-3会下雪和雨,也就是说,2-3是有用的部分,其他部分你不能实现任何天气(不是)。因此,方法是再次检查数组。从第二个开始,如果和小于总人数,则表示可以放下(不能重叠)。如果大于总人数,我们只留下重叠的部分,其余的丢失,即和-总人数,然后继续…
这样做很神奇吗?
#include using namespace std; long long a[10001], b[100001]; const int N = 1e9 1; int main() {
int t; int n, m; cin >> t; while (t--) {
long long l1 = 0, r1 = N; long long l2 = 0, r2 = N; cin >> n >> m; for (int i = 1; i <= n; i ) {
cin >> a[i]; b[i] = m - a[i]; l1 = a[i]; l2 = b[i]; r1 = min(r1, a[i]); r2 = min(r2, b[i])
;
if
(i
>
1
)
{
if
(l1
<= m
) l1
=
0
;
else l1
-
= m
;
if
(l2
<= m
) l2
=
0
;
else l2
-
= m
;
}
} cout
<< l1
<<
' '
<< r1
<< endl
; cout
<< l2
<<
' '
<< r2
<< endl
;
}
return
0
;
}