题意: 安排一个序列,该序列每个数有俩个属性:t[i]、val[i]。计算一个点的价值:到目前为止的总时间*val[i].,,求 安排顺序后使得 计算所有点的价值之和最小。
思路:对于任意相邻俩项,考虑他俩顺序对总体的影响:前面的和后面的必然不变,设 他俩为 i,j. 俩种情况作差得:t/val小,就小。所以可以按之排序,则总体最小。
#include#include #include using namespace std;struct kinds{ int t; int val; double bi;};bool my(kinds a,kinds b){ return a.bi >n) { vector v(n); for(int i=0;i >v[i].t; for(int i=0;i >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