[USACO 2010 Mar S]Need For Speed

Consider a race car with initial F=1500 and M=100. Four parts are available for enhancement: i F_i M_i 1 250 25 2 150 9 3 120 5 4 200 8 Adding just part 2, e.g., would result in an acceleration of (1500+150)/(100+9) = 1650/109 = 15.13761. Below is a chart of showing the acceleration for all possible combinations of adding/not-adding the four parts (in column one, 1=part added, 0=part not added): Parts Aggregate Aggregate 1234 F M F/M 0000 1500 100 15.0000 0001 1700 108 15.7407 0010 1620 105 15.4286 0011 1820 113 16.1062 0100 1650 109 15.1376 0101 1850 117 15.8120 0110 1770 114 15.5263 0111 1970 122 16.1475 <-- highest F/M 1000 1750 125 14.0000 1001 1950 133 14.6617 1010 1870 130 14.3846 1011 2070 138 15.0000 1100 1900 134 14.1791 1101 2100 142 14.7887 1110 2020 139 14.5324 1111 2220 147 15.1020 Thus, the best additional part combination is parts 2, 3, and 4.

* Lines 1..P: The index values of P extra parts, one per line, that Bessie should add to her racecar. If she should not add any, output 'NONE' (without quotes). The output should be given in increasing order, so if the optimal set of parts is {2,4,6,7}, then the output should be in the order 2,4,6,7 and not, for example, 4,2,7,6. Solutions will be unique.

C++(g++ 7.5.0) 解法, 执行用时: 10ms, 内存消耗: 488K, 提交时间: 2023-08-09 16:00:48

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAX=1e9+7;
const int N=1e4+5;
int fi[N],mi[N];
int f0,m0,n;
int check(double a){
	double sum=f0-m0*a;
	double t;
	for(int i=0;i<n;i++){
		t=fi[i]-a*mi[i];
		if(t>0)sum+=t;
	}
	if(sum>=0)return 1;
	else return 0;
}
int main(){	
	cin>>f0>>m0>>n;
	for(int i=0;i<n;i++){
		cin>>fi[i]>>mi[i];
	}
	double l=0,r=MAX;
	ll mid;
	for(int i=0;i<100;i++){
		mid=(l+r)/2;
		if(check(mid)){
			l=mid;
		}else{
			r=mid;
		}
	}
	int cnt=0;
//	cout<<l<<endl;
	for(int i=0;i<n;i++){
		if(fi[i]-l*mi[i]>0){
			cout<<i+1<<endl;
			cnt++;
		}
	}
	if(cnt==0)cout<<"NONE\n";
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 6ms, 内存消耗: 488K, 提交时间: 2019-10-28 15:37:41

#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
double l,r,mi,F,M,f[11000],m[11000],eps=1e-6,re,te,sum;
int n;
bool b[11000],op;
inline bool check(double k){
	re=F-k*M;
	sum=0;
	fo(i,1,n){
		te=-f[i]+k*m[i];
		if (te<0){
			sum+=te;
			b[i]=1;
		}else b[i]=0;
	}
	return re>=sum;
}
int main(){
	scanf("%lf%lf%d",&F,&M,&n);
	fo(i,1,n) scanf("%lf%lf",&f[i],&m[i]);
	l=0;r=1e6;
	while (l+eps<r){
		mi=(l+r)*0.5;
		if (check(mi)) l=mi;else r=mi;
	}
	fo(i,1,n) if (b[i]){
		printf("%d\n",i);
		op=1;
	}
	if (!op) printf("NONE\n");
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 8ms, 内存消耗: 384K, 提交时间: 2019-10-26 10:28:26

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int MAXN=10010;

int n,M,F,f[MAXN],m[MAXN];

inline bool check(double x){
	double sum=F-M*x;
	for(int i=1;i<=n;++i)
		sum+=max(0.0,f[i]-m[i]*x);
	return sum>=0;
}

int main()
{
	scanf("%d%d%d",&F,&M,&n);
	for(int i=1;i<=n;++i)
		scanf("%d%d",&f[i],&m[i]);
	double l=0,r=1e18;
	while(r-l>0.001){
		double mid=(l+r)/2.0;
		if(check(mid)) l=mid;
		else r=mid;
	}
	bool flag=0;
	for(int i=1;i<=n;++i)
		if(f[i]-m[i]*l>0) printf("%d\n",i),flag=1;
	if(!flag) puts("NONE");
	return 0;
}

详情