题意
\(n\)个人,每个人有一个亲密值\(v_{i}\)和等待时间\(t_{i}\),每个人的花费是前面所有人包括自己的等待时间和乘亲密值,求所有人花费的最小值
数据范围
\(0 < n < 100000\)
\(0 \leq v_{i},t_{i} \leq 10000\)
题解
考虑有两个人\(i,j\)的情况
- \(i\)在前:\(v_{i} · t_{i} + v_{j} · (t_{i}+t_{j})\)
- \(j\)在前:\(v_{j} · t_{j} + v_{i} · (t_{i}+t_{j})\)
展开后分别是
- \(i\)在前:\(v_{i} · t_{i} + v_{j} · t_{i} + v_{j} · t_{j}\)
- \(j\)在前:\(v_{j} · t_{j} + v_{i} · t_{i} + v_{i} · t_{j}\)
去掉相同项\(v_{i} · t_{i} + v_{j} · t_{j}\)后为
- \(i\)在前:$v_{j} · t_{i} $
- \(j\)在前:\(v_{i} · t_{j}\)
如果\(v_{j} · t_{i} < v_{i} · t_{j}\)
即\(\frac{v_{j}}{t_{j}} < \frac{v_{i}}{t_{i}}\)
可以得到比值大的在前面得到的总花费最小
Code
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ll long long
const int N=1e5+10;
int n;
struct Node{
int v;
int t;
long long num=0;
double val;
bool operator < (const Node &t) const {
if(val==t.val)
return v>t.v;
return val>t.val;
}
}e[N];
int main( )
{
ll sum=0;
cin>>n;
ll pre_sum=0;
rep(i,1,n+1){
scanf("%d%d",&e[i].v,&e[i].t);
e[i].val=(double)e[i].v/e[i].t;
}
sort(e+1,e+n+1);
rep(i,1,n+1){
pre_sum+=e[i].t;
sum+=e[i].v*pre_sum;
}
printf("%lld\n",sum);
return 0;
}
原文链接: https://www.cnblogs.com/hhyx/p/13210187.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/360421
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!