Gym-101669G Robots (思维/水题)

思路

根据物理规律, 按照加速度降序即是最优解.
分别算出并作差即可

Code

#include <bits/stdc++.h>
using namespace std;
struct node
{
    double a, t;
    bool operator<(const node &rhs)
    {
        return a > rhs.a;
    }
};

int main()
{
    int n;
    scanf("%d", &n);
    double ans1 = 0, ans2 = 0, ans;
    vector<node> vec;
    double v1 = 0;
    for (int i = 0; i < n; ++i)
    {
        node tmp;
        cin >> tmp.a >> tmp.t;
        vec.push_back(tmp);
        ans1 += v1 * tmp.t + 0.5 * tmp.a * tmp.t * tmp.t;
        v1 += tmp.a * tmp.t;
    }
    v1 = 0;
    sort(vec.begin(), vec.end());
    for (int i = 0; i < n; ++i)
    {
        ans2 += v1 * vec[i].t + 0.5 * vec[i].a * vec[i].t * vec[i].t;
        v1 += vec[i].a * vec[i].t;
    }
    ans = ans2 - ans1;
    printf("%.1lf
", ans);
}