[TOIP 2023] 裁員風暴

ID: 11496

远端评测题

1000ms

512MiB

尝试: 0

已通过: 0

难度: 3

上传者:

root

标签>

二分

2023

双指针 two-pointer

台湾

题目描述

孫執行長任職於美味蛋糕股份有限公司，因為今年財報不如預期股東寄了公開信呼應公司能刪減成本，孫執行長決定要讓公司一些夥伴走自己的路。

孫執行長列出 $n$ 個公司目標，並請員工們各自從 $n$ 個公司目標挑 $1$ 個或 $2$ 個他們認為最重要的目標，做出相同選擇的員工會被分類到同一個小組。已知每種可能的目標組合都至少有一位員工選擇，可以計算出恰選擇 $1$ 個目標的小組有 $n$ 組，恰選擇 $2$ 個目標的小組有 $\frac{n(n-1)}{2}$ 組，合計共有 $n + \frac{n(n-1)}{2} = \frac{n(n+1)}{2}$ 個小組。

透過 AI 大數據分析，每個公司目標都被 AI 賦予一個權重，這裡用 $w_i$ 來表示第 $i$ 的公司目標的權重。並且我們可以用一個 $01$ -序列 $y$ 序列： $y_1, y_2, \cdots, y_n$ 來表示一個小組所選擇的目標，有選擇第 $i$ 個公司目標則 $y_i = 1$ ，否則 $y_i = 0$ 。 AI 定義裁指數為：

\left( \dfrac{\displaystyle \sum_{i=1}^{n}w_i\times y_i}{\displaystyle \sum_{j=1}^{n} y_j} \right)

孫執行長決定把所有小組的裁指數排名，如果一個人所屬於裁指數前 $k$ 大的小組就予以開除。

想請你幫忙孫執行長找出排序後第 $k$ 大的裁指數。

例如： $n=3$ 而 $k=4$ ， $w_1=5, w_2=-2, w_3=3$ ，會有 $\dfrac{3(3+1)}{2} = 6$ 個小組，每個小組的裁指數如下表 :

$y_1$	$y_2$	$y_3$	裁指數
$0$	$0$	$1$	$(0+0+3)/(0+0+1) = 3$
	$1$	$0$	$(0-2+0)/(0+1+0) = -2$
	$1$	$1$	$(0-2+3)/(0+1+1) = \frac{1}{2}$
$1$	$0$	$0$	$(5+0+0)/(1+0+0) = 5$
	$0$	$1$	$(5+0+3)/(1+0+1) = 4$
	$1$	$0$	$(5-2+0)/(1+1+0) = \frac{3}{2}$

裁指數排序後為 $-2, \frac{1}{2}, \frac{3}{2}, 3, 4, 5$ ，並且第 $4$ 大為 $\frac{3}{2}$ 。（備註：如果裁指數排名第 $k$ 大和第 $k+1$ 大的裁指數相等，那孫執行長會另外想方法決定裁員名單，不需替他擔心）

输入数据 1

3 4
5 -2 3

输出数据 1

3
2

输入数据 2

3 3
5 -2 3

输出数据 2

3
1

输入数据 3

9 45
5 -1 2 -3 6 -9 7 3 2

输出数据 3

-9
1

#P11849. [TOIP 2023] 裁員風暴