题目:
对抗内卷(大佬经常说别再卷了)
有一门课程n个学生选,期末要写一篇论文每个同学写的字数有一个下限和一个上限,课程的成绩是按学生字数的排名来给分的,排名越高分数越高,每个同学都想得到更高的成绩,而且他们都想写最少字数,那么在满足每个同学不能比原计划分数低的情况下求出所有同学总共要写的最少字数。
题解:
本题的关键在于要理解“不能比原计划的分数低”,我认为是“战胜该战胜的人”,也就是如果有的人自己肯定能超过,那就一定要超过,还是不明白继续看
如果A的上限大于B的上限,那么B永远不能超过A,只要A的字数比B的上限高即可。也就是说对于A来说B是肯定能超过的人
如果两个人的上限一样,那么就比下限,如果AB上限一样,A的下限比B的更低,为了让大家的字数都少,B就取下限,A也取下限。(B的下限是在A的范围内的,而反过来不对),也就是说当两个人不存在绝对优势时,不如大家写的一样少,即提高了排名又少了字数
现在我们根据这两个规则来确定排名(含并):按照上限降序,当上限一样时按照下限升序,这样的排序结果基本上就是他们的排名
规定一个最小字数mini,我们从最后一名同学开始,如果该同学的下限小于mini,那么他就写mini的字数,如果大于mini(说明该同学无法写到mini的子树),该同学只能写自己下限的字数,并维护新的mini,这样进行
代码:
#include<bits/stdc++.h> using namespace std; struct node{ long long a; long long b; node(){} node(long long aa,long long bb) { a=aa; b=bb; } }; bool cmp(node node1,node node2) { if(node1.b==node2.b) return node1.a<node2.a;//下限从小到大 else return node1.b>node2.b;//上限从大到小 } int main() { int n; long long ans; ans=0; node N[100005]; cin>>n; for(int i=0;i<n;i++) { long long aa,bb; cin>>aa>>bb; N[i]=node(aa,bb); } sort(N,N+n,cmp); long long minword=N[n-1].a; ans+=minword; for(int i=n-2;i>=0;i--) { if(minword>=N[i].a) { ans+=minword; } else{ minword=N[i].a; ans+=minword; } } cout<<ans<<endl; return 0; }