题解 | To Fill or Not to Fill

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn = 10000.0;
const int dist = 30005;
double jia[dist];
struct fuil{
	double num;
	double dis;
}fu[maxn];
bool cmp(fuil f1,fuil f2){
	return f1.num<f2.num;
}
int main(){
	int cm,d,davg,n;
	while(cin>>cm>>d>>davg>>n){
		for(int i=0;i<n;i++){
			cin>>fu[i].num>>fu[i].dis;
		}
		sort(fu,fu+n,cmp);
		for(int i=0;i<=d;i++)
		jia[i] = -1;
		for(int i=0;i<n;i++){
			for(int j=fu[i].dis,ge = 0;j<=d && ge<cm*davg;j++,ge++){
				if(jia[j]==-1)jia[j] = fu[i].num/(double)davg;
			}
		}
		double ans = 0;
		double flag = -1;
		for(int i=0;i<d;i++){
			if(jia[i]==-1){
				flag = i;
				break;
			}
			ans+=jia[i];
		}
		if(flag!=-1){
			printf("The maximum travel distance = %.2f\n",flag);
			continue;
		}
		printf("%.2f\n",ans);
	}
}