php和网站开发,云南网站建设价格低,直接做海报的网站,专业的团队网站建设题目#xff1a;
对抗内卷#xff08;大佬经常说别再卷了#xff09; 有一门课程n个学生选#xff0c;期末要写一篇论文每个同学写的字数有一个下限和一个上限#xff0c;课程的成绩是按学生字数的排名来给分的#xff0c;排名越高分数越高#xff0c;每个同学都想得到…题目
对抗内卷大佬经常说别再卷了 有一门课程n个学生选期末要写一篇论文每个同学写的字数有一个下限和一个上限课程的成绩是按学生字数的排名来给分的排名越高分数越高每个同学都想得到更高的成绩而且他们都想写最少字数那么在满足每个同学不能比原计划分数低的情况下求出所有同学总共要写的最少字数。
题解
本题的关键在于要理解“不能比原计划的分数低”我认为是“战胜该战胜的人”也就是如果有的人自己肯定能超过那就一定要超过还是不明白继续看 如果A的上限大于B的上限那么B永远不能超过A只要A的字数比B的上限高即可。也就是说对于A来说B是肯定能超过的人 如果两个人的上限一样那么就比下限如果AB上限一样A的下限比B的更低为了让大家的字数都少B就取下限A也取下限。B的下限是在A的范围内的而反过来不对也就是说当两个人不存在绝对优势时不如大家写的一样少即提高了排名又少了字数 现在我们根据这两个规则来确定排名含并按照上限降序当上限一样时按照下限升序这样的排序结果基本上就是他们的排名 规定一个最小字数mini我们从最后一名同学开始如果该同学的下限小于mini那么他就写mini的字数如果大于mini说明该同学无法写到mini的子树该同学只能写自己下限的字数并维护新的mini这样进行
代码
#includebits/stdc.husing namespace std;struct node{long long a;long long b;node(){}node(long long aa,long long bb){aaa;bbb;}};bool cmp(node node1,node node2){if(node1.bnode2.b)return node1.anode2.a;//下限从小到大 elsereturn node1.bnode2.b;//上限从大到小 }int main(){int n;long long ans;ans0;node N[100005];cinn;for(int i0;in;i){long long aa,bb;cinaabb;N[i]node(aa,bb);}sort(N,Nn,cmp);long long minwordN[n-1].a;ansminword;for(int in-2;i0;i--){if(minwordN[i].a){ansminword;}else{minwordN[i].a;ansminword;} }coutansendl;return 0;}
