打卡信奥刷题（3626）用C++实现信奥题 P11849 [TOIP 2023] 裁员风暴

P11849 [TOIP 2023] 裁员风暴题目描述孙执行官任职于美味蛋糕股份有限公司由于今年财报未达预期股东寄了公开信呼吁公司削减成本孙执行官决定让公司部分伙伴走自己的路。孙执行官列出nnn个公司目标并请员工们各自从nnn个公司目标挑选111个或222个他们认为最重要的目标。做出相同选择的员工会被分类到同一个小组。已知每种可能的目标组合都至少有一位员工选择可以计算出恰好选择111个目标的小组有nnn组恰好选择222个目标的小组有n(n−1)2\frac{n(n-1)}{2}2n(n−1)​组合计共有nn(n−1)2n(n1)2n \frac{n(n-1)}{2} \frac{n(n1)}{2}n2n(n−1)​2n(n1)​个小组。通过 AI 大数据分析每个公司目标都被 AI 赋予一个权重这里用wiw_iwi​表示第iii个公司目标的权重。我们可以用一个010101-序列yyyy1,y2,⋯ ,yny_1, y_2, \cdots, y_ny1​,y2​,⋯,yn​来表示一个小组所选择的目标选择第iii个目标则yi1y_i 1yi​1否则yi0y_i 0yi​0。AI 定义裁减指数为(∑i1nwi×yi∑j1nyj)\left( \dfrac{\displaystyle \sum_{i1}^{n}w_i\times y_i}{\displaystyle \sum_{j1}^{n} y_j} \right)​j1∑n​yj​i1∑n​wi​×yi​​​孙执行官决定将所有小组的裁减指数排名属于裁减指数前kkk大小组的员工将被开除。请你帮助孙执行官找出排序后第kkk大的裁减指数。例如当n3n3n3k4k4k4w15,w2−2,w33w_15, w_2-2, w_33w1​5,w2​−2,w3​3时共有3(31)26\dfrac{3(31)}{2} 623(31)​6个小组各小组裁减指数如下表y1y_1y1​y2y_2y2​y3y_3y3​裁减指数000000111(003)/(001)3(003)/(001) 3(003)/(001)3000111000(0−20)/(010)−2(0-20)/(010) -2(0−20)/(010)−2000111111(0−23)/(011)0.5(0-23)/(011)0.5(0−23)/(011)0.5111000000(500)/(100)5(500)/(100) 5(500)/(100)5111000111(503)/(101)4(503)/(101) 4(503)/(101)4111111000(5−20)/(110)1.5(5-20)/(110)1.5(5−20)/(110)1.5裁减指数排序后为−2,0.5,1.5,3,4,5-2, 0.5, 1.5, 3, 4, 5−2,0.5,1.5,3,4,5第444大的值为1.51.51.5。备注若第kkk大与第k1k1k1大的裁减指数相同孙执行官会另行决定裁员名单不需要替他担心输入格式nnnkkkw1w_1w1​w2w_2w2​⋯\cdots⋯wnw_nwn​nnn表示公司目标数量kkk表示需要查询的排名wiw_iwi​表示第iii个目标的权重输出格式pppqqqpq\dfrac{p}{q}qp​表示第kkk大的裁减指数ppp必须为整数qqq必须为正整数∣p∣|p|∣p∣与qqq必须互质输入输出样例 #1输入 #13 4 5 -2 3输出 #13 2输入输出样例 #2输入 #23 3 5 -2 3输出 #23 1输入输出样例 #3输入 #39 45 5 -1 2 -3 6 -9 7 3 2输出 #3-9 1说明/提示测试数据限制1≤n≤2×1051 \le n \le 2\times 10^51≤n≤2×1051≤k≤n(n1)21 \le k \le \dfrac{n(n1)}{2}1≤k≤2n(n1)​−109≤wi≤109-{10}^9 \le w_i \le {10}^9−109≤wi​≤109所有输入均为整数评分说明本题共有六个子任务限制条件如下。每个子任务需通过全部测试数据方可得分。子任务分数额外限制15n≤20n \le 20n≤2025n≤104n \le 10^4n≤104且k≤2×105k \le 2\times 10^5k≤2×10535n≤104n \le 10^4n≤104440k≤2×105k \le 2\times 10^5k≤2×105514−100≤wi≤100-100 \le w_i \le 100−100≤wi​≤100631无额外限制C实现#includebits/stdc.husingnamespacestd;#defineintlonglong//不是什么好习惯intn,k;intp[200005];boolcheck(intx){intpos0;intl1,rn;for(l;ln;l){if(rl)rl-1;while(p[l]p[r]xrl)r--;posn-r;}returnposk;}signedmain(){cinnk;for(inti1;in;i)cinp[i];sort(p1,pn1);intl-2e9,r2e9;//这里二分的是答案的2倍while(lr){intmidlr1;mid1;if(check(mid))rmid-1;elselmid;}if(l%20)coutl/2endl1endl;elsecoutlendl2endl;//特判l和2互质return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容