问题标题: 酷町堂：5238 旅行家的预算洛谷AC结果KDTwa了

5238   旅行家的预算

——————————————————————————————————

洛谷AC，结果KDT竟然WA了一个包/qwq

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#define out "No Solution"
using namespace std;

double d1, c, d2, p, ans, rest_c;
int n;

struct stu {
    double len, doller;
}a[15];

bool cmp(stu x, stu y) {
    return x.len < y.len;
}

int main() {
    cin >> d1 >> c >> d2 >> p >> n;
    for(int i=1; i<=n; i++)
        cin >> a[i].len >> a[i].doller;
    sort(a+1, a+n+1, cmp);
    a[0].len = 0, a[0].doller = p;
    n ++;
    a[n].len = d1, a[n].doller = 0;
    int i = 0;
    double need = 0, add = 0;
    while(i < n) {
        // cout << i << endl;
        if(a[i+1].len - a[i].len > c*d2) {
            cout << out;
            return 0;
        }
        int idx = i + 1; bool find = false;
        while(idx <= n && a[idx].len - a[i].len < c*d2) {
            if(a[idx].doller <= a[i].doller) {
                find = !find;
                break;
            }
            idx ++;
        }
        if(find == true) {
            need = (a[idx].len - a[i].len) /d2;
            if(rest_c >= need) {
                rest_c -= need;
            } else {
                add = need - rest_c;
                rest_c = rest_c + add - need;
                ans += add * a[i].doller;
            }
            //cout << i << " " << idx << endl;
        } else {
            int j = i + 1, mind = 0x3f3f3f3f;
            while(j <= n && a[j].len - a[i].len < c*d2) j ++;
            idx = j - 1;
            add = c - rest_c;
            rest_c = c - (a[idx].len - a[i].len) / d2;
            ans += add * a[i].doller;
            //cout << i << " " << idx << endl;
            // cout << i << endl;
        }
        i = idx;
    }
    printf("%.2f", (long long)(ans*100 + 0.5) / 100.0); 
    return 0;
}

贪心