k185. pB. 裁員風暴 (storm)
Tags : 二分搜 雙指針
Accepted rate : 49人/58人 ( 84% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-03-22 00:04

Content

題目敘述 : https://drive.google.com/file/d/1nDZNGCptQGcAZDxqRGcNt_wpz31clODZ/view?usp=sharing

孫執行長任職於美味蛋糕股份有限公司,因為今年財報不如預期股東寄了公開信呼應公司能刪減成本,孫執行長決定要讓公司一些夥伴走自己的路。
孫執行長列出 $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, · · · , y_n$ 來表示一個小組所選擇的目標,有選擇第 $i$ 個公司目標則 $y_i = 1$,否則 $y_i = 0$。$AI$ 定義裁指數為:


孫執行長決定把所有小組的裁指數排名,如果一個人所屬於裁指數前 $k$ 大的小組就予以開除。想請你幫忙孫執行長找出排序後第 $k$ 大的裁指數。

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

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

測資限制

• $1 ≤ n ≤ 2 × 10^5$。
• $1 ≤ k ≤ \frac{n(n + 1)}{2}$。
• $−10^9 ≤ w_i ≤ 10^9$。
• $n, k, w_i$ 都是整數。

Input
$n$ $k$
$w_1$ $w_2$ · · · $w_n$

•    $n$ 代表公司目標數量。
•    $k$ 代表孫執行長的想知道的排名。
•    $w_i$ 代表第 $i$ 個公司目標的權重。

Output
$p$
$q$

•   $\frac{p}{q}$ 代表排序後第 $k$ 大的裁指數。
•   $p$ 必須為整數。
•   $q$ 必須為正整數。
•   $|p|$ 跟 $q$ 必須互質。

Sample Input #1
3 4
5 -2 3
Sample Output #1
3
2
Sample Input #2
3 3
5 -2 3
Sample Output #2
3
1
Sample Input #3
9 45
5 -1 2 -3 6 -9 7 3 2
Sample Output #3
-9
1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (2%): 1.0s , <1K
公開 測資點#1 (3%): 1.0s , <1K
公開 測資點#2 (2%): 1.0s , <1M
公開 測資點#3 (3%): 1.0s , <1M
公開 測資點#4 (2%): 1.0s , <1M
公開 測資點#5 (3%): 1.0s , <1M
公開 測資點#6 (20%): 1.0s , <1M
公開 測資點#7 (20%): 1.0s , <10M
公開 測資點#8 (7%): 1.0s , <1M
公開 測資點#9 (7%): 1.0s , <1M
公開 測資點#10 (3%): 1.0s , <10M
公開 測資點#11 (3%): 1.0s , <10M
公開 測資點#12 (3%): 1.0s , <10M
公開 測資點#13 (3%): 1.0s , <1M
公開 測資點#14 (3%): 1.0s , <1M
公開 測資點#15 (3%): 1.0s , <1M
公開 測資點#16 (3%): 1.0s , <1M
公開 測資點#17 (3%): 1.0s , <1M
公開 測資點#18 (3%): 1.0s , <10M
公開 測資點#19 (4%): 1.0s , <10M
Hint :

題目和測資來源 : twpca

注意因為礙於系統問題測試資料沒辦法完整的放上。

 

子任務 分數 額外輸入限制測資點
15$n ≤ 20$#00~#01
25$n ≤ 10^4$ 且 $k ≤ 2 × 10^5$#02~#03
35$n ≤ 10^4$#04~#05
440$k ≤ 2 × 10^5$#06~#07
514$−100 ≤ w_i ≤ 100$#08~#09
631無額外限制#10~#19

 

如果題目有問題歡迎來信詢問!

Tags:
二分搜 雙指針
出處:
TOI入營考2023 [管理者: Ststone1687 (Ststone) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」