回复 6楼 xiaohuo66
#include <stdio.h>
#include <math.h>
#define max(a,b) a<b?b:a
float a[10005];
float b[10005];
float c[10005];
void Swap(int *p, int *q)
{
int buf;
buf = *p;
*p = *q;
*q = buf;
return;
}
void QuickSort(int *a, int low, int high)
{
int i = low;
int j = high;
int key = a[low];
if (low >= high) //如果low >= high说明排序结束了
{
return ;
}
while (low < high) //该while循环结束一次表示比较了一轮
{
while (low < high && key <= a[high])
{
--high; //向前寻找
}
if (key > a[high])
{
Swap(&a[low], &a[high]);
++low;
}
while (low < high && key >= a[low])
{
++low; //向后寻找
}
if (key < a[low])
{
Swap(&a[low], &a[high]);
--high;
}
}
QuickSort(a, i, low-1); //用同样的方式对分出来的左边的部分进行同上的做法
QuickSort(a, low+1, j); //用同样的方式对分出来的右边的部分进行同上的做法
}
int check(int mid,int n,int m)
{
float sum = 0;
for(int j = 1 ; j <= n ; j++)
{
c[j] = a[j] - mid*b[j];
}
QuickSort(c,c[1],c[n]);
for(int j = 1 ; j <= m ; j++)
{
sum += c[j];
}
if(sum < 0)return 1;
else return 0;
}
int main()
{
int t;
scanf("%d",&t);
for(int i = 1 ; i <= t ; i++)
{
int n,m;
float r = -1,ans = 0;
scanf("%d%d",&n,&m);
for(int j = 1 ; j <= n ; j++)
{
scanf("%f%f",&a[j],&b[j]);
r = max(a[j]/b[j],r);
}
printf("Case #%d: ",i);
float l = 0,mid;
while(r-l>0.001)
{
mid = (l+r)/2;
if(check(mid,n,m))
{
l = mid;
}
else
{
r = mid;
}
}
printf("%0.2f\n",mid);
}
return 0 ;
}
[此贴子已经被作者于2020-11-28 18:04编辑过]
