首页 > 其他分享 >Educational Round 30 题解

Educational Round 30 题解

时间:2022-10-06 20:12:14浏览次数:86  
标签:Educational 题解 30 Link 右开 Round 指针

Contest Link

虽然是 unrated,不过秉持着 Educational Round 的传统,题还是挺不错的。

A. Chores

Problem Link

评价:善用 STL。

由于 \(a\) 已经排好序了,且 \(x\le \min_{i=1}^{n}a_i\)(即将任何一个数替换为 \(x\) 都能够减少总时长),因此想到贪心。

将最耗时间的 \(k\) 个数变成 \(x\)(亦即题目中的 \(a_{n-k+1},a_{n-k+2},\ldots,a_n\)),共耗时 \(k\times x\);然后求出前 \(n-k\) 个数的和,加起来即可。

注意到 STL 中有 accumulate 函数(在 numeric 头文件中),用法为 accumulate(头指针,尾指针,初始值); 其中头尾指针如 sort 一样,是左闭右开的。于是上面的式子就是以 \(k\times x\) 为初值,对 \(1\) 至 \(n-k+1\) 中的数(左闭右开)进行求和,可以直接套用,大大减小码量。

Sample Code

标签:Educational,题解,30,Link,右开,Round,指针
From: https://www.cnblogs.com/Lyrically/p/Edu_Round_30_Solution.html

相关文章

  • 动手动脑9.30
                   动手动脑9.301. 该代码在Fooobj1=newFoo();的地方出错了,出错原因是main方法在引用变量时Foo()没有被定义,Foo类......
  • CF1415D XOR-gun 题解 二分答案/贪心
    题目链接https://codeforces.com/problemset/problem/1415/D题目大意给定一个长为\(n\)的不降序列,每次操作可以任选相邻的两个数,并将这两个数替换为两个数按位异或的......
  • C语言基础笔试题解析
    题目在这里:​​c语言笔试面试大全,C语言基础笔试题_Thomas杨大炮的博客-CSDN博客t​​2.C语言程序的三种基本结构都有哪些呢?3. ​​递归调用​​和间接递归调用​​定义​......
  • 2022.9.30 Java第四次课后总结
    1.publicclassBoxAndUnbox{ /** *@paramargs */ publicstaticvoidmain(String[]args){ intvalue=100; Integerobj=value;//装箱 intresult=obj*2;......
  • P2305 [NOI2014] 购票
    P2305[NOI2014]购票设\(f_{x}\)表示从\(x\)点跳到\(1\)的最少费用。考虑\(x\)的一个祖先\(u\),有\[f_x=f_{u}+\text{dis}_{u,x}\timesp_x+q_x\]其中需要满足......
  • CF1728A Colored Balls: Revisited 题解
    【题目传送门】思路因为球的总数为奇数,所以肯定会剩下一颗球,因此每次都往数量小的拿,那么最后剩下的球一定是最初数量最多的小球的编号。因为假设最多的少一颗,那么将可以......
  • 9.30号课下练习
    1第一个测试代码 2问题 不一样,一个是原有数据类型一个是自己定义的类。 3第二个代码块测试 4问题 构造说了算,构造比初始化加载晚。5java代码中初始化变量......
  • NOIP2015 T3 乱作题解
    题目看起来好像不是很难啊,为什么我做不出来呢;1.暴力枚举枚举x,y,z的值,再判断是否符合条件;时间复杂度:\(\mathcal{O}(n^3)\)期望得分:\(20pts\)\(Code\):#includ......
  • 9.30课堂测试
    没有使用栈来完成,不够简约,仍需改进。但是实现了继承和基本要求2年纪类packagearith;importjava.util.ArrayList;importjava.util.Scanner;importjava.util.Random;......
  • CF870E题解
    题目大意给你平面上\(n(1\leqslantn\leqslant10^5)\)个点,给出他们的坐标\(x_i,y_i(-10^9\leqslantx_i,y_i\leqslant10^9)\)。对于每个点有三种操作:不进行任何操......