自己做网站必须要学哪些,重庆新闻奖,旅游型网站开发,河北省建设厅办事大厅网站第三题#xff1a;T3工作安排
标签#xff1a;结构体排序、贪心算法 题意#xff1a;有 n n n份任务。完成第 i i i份任务需要 t i t_i ti的时间#xff0c;在这份任务没有完成之前#xff0c;每一个单位时间会收到 f i f_i fi单位的罚款。求以什么顺序安排这些任务T3工作安排
标签结构体排序、贪心算法 题意有 n n n份任务。完成第 i i i份任务需要 t i t_i ti的时间在这份任务没有完成之前每一个单位时间会收到 f i f_i fi单位的罚款。求以什么顺序安排这些任务才能使罚款总额最少 数据范围 1 n , t i , f i 200 , 000 1n,\ t_i,\ f_i200,000 1n, ti, fi200,000 题解这道题有点像 洛谷P1012 [NOIP1998 提高组] 拼数 这道题。本质来说就是进行结构体排序的时候比较的内容不再是简单的两个对象比如代码里面 x x x和 y y y各自的数据内容而是说需要两者结合进行比较。 像这道题有两份任务 x x x和 y y y我到底是把 x x x先完成还是先把 y y y先完成我们需要考虑到先完成 x x x任务那对于 y y y来说就得等 x . t x.t x.t的时间那罚款就是 x . t ∗ y . f x.t*y.f x.t∗y.f同理先完成 y y y任务对于 x x x来说的罚款是 y . t ∗ x . f y.t*x.f y.t∗x.f我们需要贪心的考虑哪种所带来的罚款会少点。 还有个细节就是等待时间应该是累积的对于第 i i i项任务没完成之前需要收到罚款的时间是前 i i i项任务时间之和。 代码
#include bits/stdc.h
using namespace std;typedef long long ll;
struct node {ll t, f;
}p[200005];bool cmp(node x, node y) {return x.t * y.f y.t * x.f;
}int main() {ll n, sum 0, ans 0;cin n;for (int i 1; i n; i) {cin p[i].t p[i].f;}sort(p 1, p 1 n, cmp);for (int i 1; i n; i) {sum p[i].t;ans p[i].f * sum;}cout ans endl;return 0;
}
