题意分析

题目要求我们在给定的 $n$次考试中，选择放弃 $k$次考试后，使得剩下的 $n-k$次考试的累计平均分最大化。累计平均分的计算方式是所有保留考试的答对题数之和除以总题数之和：

$$\text{Average} = \frac{\sum_{i \in S} a_i}{\sum_{i \in S} b_i} $$

其中 $S$是保留的考试集合。

解题思路

关键观察

我们需要最大化这个分数：

$$\frac{\sum_{i \in S} a_i}{\sum_{i \in S} b_i}$$

这类似于经典的分数规划问题（Fractional Programming），可以通过二分法来求解。

分数规划方法

设目标平均分为 $x$，我们需要判断是否存在一个子集 $S$使得：

$$\frac{\sum_{i \in S} a_i}{\sum_{i \in S} b_i} \geq x $$

可以转化为：

$$\sum_{i \in S} (a_i - x \cdot b_i) \geq 0$$

因此，我们可以通过二分法来寻找最大的 $x$使得存在至少 $n-k$个考试满足上述不等式。

具体步骤

1. 二分搜索范围初始化：

   • $lb = 0$（最低可能平均分）
   • $ub = 10^9$（最高可能平均分）

2. 二分过程：

   • $mid = \frac{lb + ub}{2}$
   • $y_i = a_i - mid \cdot b_i$（计算每个考试的贡献）
   • $y_i$越大表示该考试对提高平均分的贡献越大。
   • $sort(y_i)$降序排序后取前 $n-k$个最大的 $y_i$求和。
   • $sum(y_i) \geq 0$说明当前 $mid$可行，可以尝试更大的值；否则需要减小。

3. 终止条件：

   • $ub - lb$足够小或迭代足够多次后停止。

代码解析

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;
const int maxn=1005;
const int INF=0x3f3f3f3f;
int N,M;
int w[maxn],v[maxn]; // w是b_i（总题数），v是a_i（答对题数）

double y[maxn];// v_i - x * w_i

bool cmp(double a, double b)
{
    return a>b;//降序排序大的在前；
}

bool C(double x)
{
    for(int i=0;i<N;i++)
        y[i]=v[i]-x*w[i];//计算每个考试的贡献值；
    
    sort(y,y+N,cmp);//降序排序；

    
    double sum=0;
    
    for(int i=0;i<N-M;i++)//取前N-M个最大的贡献值；
        sum+=y[i];
    
   
    
    return sum>=0;//如果总和>=0说明x可行；
}

int main()
{
    
   
    
     while(cin>>N>>M&&(N||M))
     {
         for(int i=0;i<N;i++)
             cin>>v[i];
         for(int i=0;i<N;i++)
             cin>>w[i];
         
         double lb=0,ub=INF;//二分上下界；
         
         for(int i=0;i<100;i++)//迭代100次保证精度；
         {
             double mid=(lb+ub)/2;
             if(C(mid))lb=mid;//如果mid可行尝试更大的；
             else ub=mid;//否则减小；
             
         }
        
         printf("%.0f\n",lb*100);//四舍五入输出百分比；
     }
}

复杂度分析

• 时间复杂度: 每次二分判断需要排序 $O(n\log n)$，共进行约100次二分迭代。总复杂度为 $O(100 \cdot n\log n)$。

• 空间复杂度: 额外数组 $y$占用 $O(n)$空间。

总结

本题通过分数规划结合二分法高效求解了最优平均分问题。核心在于将原问题转化为判定性问题并通过排序快速计算前 $n-k$大的贡献值。