首页 > 代码库 > hdu 4882 /按排顺序使序列最优问题
hdu 4882 /按排顺序使序列最优问题
题意: 安排一个序列,该序列每个数有俩个属性:t[i]、val[i]。计算一个点的价值:到目前为止的总时间*val[i].,,求 安排顺序后使得 计算所有点的价值之和最小。
思路:对于任意相邻俩项,考虑他俩顺序对总体的影响:前面的和后面的必然不变,设 他俩为 i,j. 俩种情况作差得:t/val小,就小。所以可以按之排序,则总体最小。
#include<iostream> #include<vector> #include<algorithm> using namespace std; struct kinds { int t; int val; double bi; }; bool my(kinds a,kinds b) { return a.bi<b.bi; } int main() { int n; while(cin>>n) { vector<kinds>v(n); for(int i=0;i<n;i++) cin>>v[i].t; for(int i=0;i<n;i++) { cin>>v[i].val; v[i].bi=v[i].t*1.0/v[i].val; } sort(v.begin(),v.end(),my); long long sum=0; long long sumt=0; for(int i=0;i<n;i++) { sumt+=v[i].t; sum+=v[i].val*sumt; } cout<<sum<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。