首页 > 代码库 > 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;
}