Dropping Test

Luogu

IDLGP10505

Time1000ms

Memory512MB

DifficultyP3

二分O2优化分数规划

在某个课程中，你需要进行 $n$ 次测试。如果你在共计 $b_i$ 道题的测试 $i$ 上的答对题目数量为 $a_i$，你的累积平均成绩就被定义为 $$100\times \dfrac{\displaystyle \sum_{i=1}^n a_i}{\displaystyle \sum_{i=1}^n b_i}$$ 给定您的考试成绩和一个正整数 $k$，如果您被允许放弃任何 $k$ 门考试成绩，您的累积平均成绩的可能最大值是多少。假设您进行了 $3$ 次测试，成绩分别为 $5/5,0/1$ 和 $2/6$。在不放弃任何测试成绩的情况下，您的累积平均成绩是 $$100\times \frac{5+0+2}{5+1+6} \approx 58.33 \approx 58$$ 然而，如果你放弃第三门成绩，则您的累积平均成绩就变成了 $$100\times \frac{5+0}{5+1}\approx 83.33\approx 83$$ ## Input 输入包含多组测试用例，每个测试用例包含三行。对于每组测试用例，第一行包含两个整数 $n$ 和 $k$。第二行包含 $n$ 个整数，表示所有的 $a_i$。第三行包含 $n$ 个整数，表示所有的 $b_i$。当输入用例 $n=k=0$ 时，表示输入终止，且该用例无需处理。 ## Output 对于每个测试用例，输出一行结果，表示在放弃 $k$ 门成绩的情况下，可能的累积平均成绩最大值。结果应四舍五入到最接近的整数。 [samples] ## Note 数据范围 $1 \le n \le 1000$, $0 \le k < n$, $0 \le a_i \le b_i \le 10^9$。

Samples

Input #1

Output #1

83
100

API Response (JSON)

{
  "problem": {
    "name": "Dropping Test",
    "description": {
      "content": "在某个课程中，你需要进行 $n$ 次测试。  如果你在共计 $b_i$ 道题的测试 $i$ 上的答对题目数量为 $a_i$，你的累积平均成绩就被定义为 $$100\\times \\dfrac{\\displaystyle \\sum_{i=1}^n a_i}{\\displaystyle \\sum_{i=1}^n b_i}$$ 给定您的考试成绩和一个正整数 $k$，如果您被允许放弃任何 $k$ 门考",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10505"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在某个课程中，你需要进行 $n$ 次测试。 \n\n如果你在共计 $b_i$ 道题的测试 $i$ 上的答对题目数量为 $a_i$，你的累积平均成绩就被定义为\n\n$$100\\times \\dfrac{\\displaystyle \\sum_{i=1}^n a_i}{\\displaystyle \\sum_{i=1}^n b_i}$$\n\n给定您的考试成绩和一个正整数 $k$，如果您被允许放弃任何 $k$ 门考...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments