题目

站外题

我的代码

#include<bits/stdc++.h>
using namespace std;
int n,k;
struct _{
	long long v;
	long long w;
	int hao;
} a[100005];
bool cmp(_ x,_ y){
	//return x.v/x.w>y.v/y.w;
	if (x.v*y.w==y.v*x.w) return x.v<y.v;
	return x.v*y.w>y.v*x.w;
}
int main(){
	cin>>n>>k;
	for (int i=1;i<=n;i++){
		scanf("%lld %lld",&a[i].v,&a[i].w);
		a[i].hao=i;
	}
	sort(a+1,a+1+n,cmp);
	for (int i=1;i<=k;i++) cout<<a[i].hao<<" ";
	return 0;
}

标程

#include <bits/stdc++.h>
using namespace std; 
double eps = 1e-8; 
int n,k; 
struct stu{ double v,w; double z; int xia; }; 
stu v[1000000]; 
double a[1000000]; 
int cmp(double x,double y){ return x - y > eps; } 
int cmp2(stu x,stu y){ return x.z - y.z > eps; } 
int main(){
	scanf("%d%d",&n,&k); 
	for(int i = 1;i <= n;i ++){ 
		scanf("%lf%lf",&v[i].v,&v[i].w); 
		v[i].xia = i; 
	} 
	double l = 0,r = 10000100; 
	double mid; 
	double ans; 
	while(fabs(l - r) > eps){ 
		mid = (l + r) / 2; 
		for(int i = 1;i <= n;i ++){ 
			a[i] = v[i].v - v[i].w * mid; 
		} 
		sort(a + 1,a + 1 + n,cmp); 
		double cnt = 0; 
		for(int i = 1;i <= k;i ++){ 
			cnt += a[i]; 
		} 
		if(cnt >= 0){ 
			l = mid; 
			ans = mid; 
		}else{ 
			r = mid; 
		} 
	} 
	for(int i = 1;i <= n;i ++){ 
		v[i].z = v[i].v - v[i].w * ans; 
	} 
	sort(v + 1,v + 1 + n,cmp2); 
	for(int i = 1;i <= k;i ++){ 
		printf("%d ",v[i].xia); 
	} 
	return 0; 
}