打卡信奥刷题（3333）用C++实现信奥题 P9350 [JOI 2023 Final] 宣传 2 / Advertisement 2

P9350 [JOI 2023 Final] 宣传 2 / Advertisement 2题目描述JOI 王国有NNN位居民编号从111到NNN。居民iii(1≤i≤N1 \le i \le N1≤i≤N) 住在实数轴上的坐标XiX_iXi​处其影响力为EiE_iEi​。可能有多个居民住在同一坐标处。拥有较大影响力的居民具有较高的广告潜力但这样的居民在购买书籍时很谨慎。Rie 出版了一本信息学的书。为了鼓励更多人购买这本书她可以向一些居民赠送这本书的副本。如果她向居民iii(1≤i≤N1 \le i \le N1≤i≤N) 赠送了一本书居民iii将获得 Rie 的书。此外在尚未获得书的居民中满足以下条件的每位居民jjj(1≤j≤N1 \le j \le N1≤j≤N) 都会购买一本书并获得它。居民iii和居民jjj在实数轴上的距离小于或等于Ei−EjE_i - E_jEi​−Ej​。换句话说满足∣Xi−Xj∣≤Ei−Ej|X_i - X_j| \le E_i - E_j∣Xi​−Xj​∣≤Ei​−Ej​。如果所有居民都阅读了 Rie 的书信息学奥林匹克将得到极大的认可。编写一个程序计算需要向多少位居民赠送 Rie 的书才能使 JOI 王国的所有居民都获得 Rie 的书。输入格式从标准输入读取以下数据。NNNX1X_1X1​E1E_1E1​X2X_2X2​E2E_2E2​⋮\vdots⋮XNX_NXN​ENE_NEN​输出格式向标准输出写入一行。输出应包含需要赠送 Rie 的书的最少居民数量以便 JOI 王国的所有居民都获得 Rie 的书。输入输出样例 #1输入 #14 4 2 2 3 3 4 6 5输出 #12输入输出样例 #2输入 #23 7 10 10 10 7 10输出 #22输入输出样例 #3输入 #310 31447678 204745778 430226982 292647686 327782937 367372305 843320852 822224390 687565054 738216211 970840050 766211141 563662348 742939240 103739645 854320982 294864525 601612333 375952316 469655019输出 #35说明/提示样例样例 1例如如果 Rie 按以下方式赠送书JOI 王国的所有居民将获得 Rie 的书。Rie 向居民 3 赠送了一本书。因为∣X3−X1∣1|X_3 - X_1| 1∣X3​−X1​∣1且E3−E12E_3 - E_1 2E3​−E1​2居民 1 会购买一本 Rie 的书并获得它。因为∣X3−X2∣1|X_3 - X_2| 1∣X3​−X2​∣1且E3−E21E_3 - E_2 1E3​−E2​1居民 2 会购买一本 Rie 的书并获得它。因为∣X3−X4∣3|X_3 - X_4| 3∣X3​−X4​∣3且E3−E4−1E_3 - E_4 -1E3​−E4​−1居民 4 不会购买 Rie 的书。因此居民 1、2、3 将获得 Rie 的书。Rie 向居民 4 赠送了一本书。由于除了居民 4 之外的所有居民都已经获得了 Rie 的书最终 JOI 王国的所有居民都获得了 Rie 的书。由于不可能向少于两位居民赠送书以使 JOI 王国的所有居民都获得 Rie 的书因此输出 2。此样例输入满足子任务 2、3、4 的约束。样例 2此样例输入满足所有子任务的约束。样例 3此样例输入满足子任务 2、3、4 的约束。约束1≤N≤5×1051 \le N \le 5 \times 10^51≤N≤5×105。1≤Xi≤1091 \le X_i \le 10^91≤Xi​≤109(1≤i≤N1 \le i \le N1≤i≤N)。1≤Ei≤1091 \le E_i \le 10^91≤Ei​≤109(1≤i≤N1 \le i \le N1≤i≤N)。给定值均为整数。子任务(10 分)E1E2⋯ENE_1E_2\cdotsE_NE1​E2​⋯EN​。(23 分)N≤16N \le 16N≤16。(36 分)N≤103N \le 10^3N≤103。(31 分) 无额外约束。题面翻译由 ChatGPT-4o 提供。C实现#includebits/stdc.husingnamespacestd;constintN705000;intn;longlongans0;structResident{longlongx,y;}t[N];boolcmp(Resident a,Resident b){if(a.yb.y)returna.xb.x;returna.yb.y;}intmain(){cinn;longlongX,E;for(inti1;in;i){cinXE;t[i].xE-X;t[i].yEX;}sort(t1,tn1,cmp);longlongMaxLLONG_MIN4;for(inti1;in;i){if(t[i].xMax)ans;Maxmax(Max,t[i].x);}coutans\n;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容