題目敘述 : 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$ 都是整數。
| $n$ $k$ $w_1$ $w_2$ · · · $w_n$ |
• $n$ 代表公司目標數量。
• $k$ 代表孫執行長的想知道的排名。
• $w_i$ 代表第 $i$ 個公司目標的權重。
| $p$ $q$ |
• $\frac{p}{q}$ 代表排序後第 $k$ 大的裁指數。
• $p$ 必須為整數。
• $q$ 必須為正整數。
• $|p|$ 跟 $q$ 必須互質。
3 4 5 -2 3
3 2
3 3 5 -2 3
3 1
9 45 5 -1 2 -3 6 -9 7 3 2
-9 1
公開 測資點#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
題目和測資來源 : twpca
注意因為礙於系統問題測試資料沒辦法完整的放上。
| 子任務 | 分數 | 額外輸入限制 | 測資點 |
| 1 | 5 | $n ≤ 20$ | #00~#01 |
| 2 | 5 | $n ≤ 10^4$ 且 $k ≤ 2 × 10^5$ | #02~#03 |
| 3 | 5 | $n ≤ 10^4$ | #04~#05 |
| 4 | 40 | $k ≤ 2 × 10^5$ | #06~#07 |
| 5 | 14 | $−100 ≤ w_i ≤ 100$ | #08~#09 |
| 6 | 31 | 無額外限制 | #10~#19 |
如果題目有問題歡迎來信詢問！
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||