八目鳗

问题描述

米斯蒂娅去捕捉八目鳗为开店作准备。现在，她在一个有八目鳗的池塘边。她知道池塘里的有n条八目鳗，把第i条八目鳗从池塘弄回小店需要t_i∗2个单位的时间（毕竟需要往返）。
这些八目鳗会自己吃P点！随着时间的推移，米斯琪把它们弄回来所消耗的体力与时间成正比，即在第t个时刻开始运第i条八目鳗所消耗的体力为t∗c_i，其中，c_i是给定的常数。一开始所有的八目鳗都没有P点，也就是说运送第一条八目鳗所消耗的体力为0。
米斯琪想知道把所有八目鳗运回小店所消耗的体力最少是多少。

输入格式

第一行输入一个整数n，表示八目鳗的数量。
接下来n行，每行包含两个整数t_i,c_i。

输出格式

一个整数，表示最少消耗的体力。

样例输入

3 1

2 5

2 3

3 2

4 1

1 6

样例输出

数据范围

对于10%的数据，n≤10,t≤100,c_i≤10；
对于60%的数据，n≤1000,t≤20000,c_i≤100；
对于100%的数据，n≤100000,t≤2000000,c_i≤100。

题解

假设我们已经找出消耗体力最少的方案，并将八目鳗按搬运顺序重新编号，即现在编号为i的八目鳗是第i个搬运的

设当前时刻为t，接下来要运第i-1只八目鳗和第i只八目鳗，而先运第i-1只八目鳗的条件为：t*c_i-1+(t+2*t_i-1)*c_i≤t*c_i+(t+2*t_i)*c_i-1

证明：

若先运第i-1只八目鳗，需消耗体力t*c_i-1，耗费了2*t_i-1的时间，在t+2*t_i-1时刻开始运第i只八目鳗，需消耗体力(t+2*t_i-1)*c_i

同理可得先运第i只八目鳗消耗的总体力为t*c_i+(t+2*t_i)*c_i-1

而我们已经找出消耗体力最少的方案，即我们已经知道第i-1只八目鳗在第i只八目鳗之前运，那么就需要满足先运第i-1只八目鳗消耗的总体力比先运第i只八目鳗消耗的总体力少，即t*c_i-1+(t+2*t_i-1)*c_i≤t*c_i+(t+2*t_i)*c_i-1

整理得：t_i-1*c_i≤t_i*c_i-1

读入所有数据后按这个条件排序，再依题意按顺序计算消耗的体力即可

 1 #include <algorithm>
 2 #include <cstdio>
 3 #define ll long long
 4 int n;
 5 ll ans;
 6 struct node{
 7     ll t,c;
 8 }a[100005];
 9 bool cmp(node x,node y)
10 {
11     return (x.t*y.c)<=(y.t*x.c);
12 }
13 int main()
14 {
15     int i,j;
16     ll s=0;
17     scanf("%d",&n);
18     for (i=1;i<=n;i++)
19       scanf("%lld%lld",&a[i].t,&a[i].c),
20       a[i].t*=2;
21     std::sort(a+1,a+n+1,cmp);
22     for (i=1;i<=n;i++)
23     {
24         ans+=(s*a[i].c);
25         s+=a[i].t;
26     }
27     printf("%lld",ans);
28     return 0;
29 }