Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 贴份不动点迭代法代码，复杂度接近O(n*logn)，几乎只要常数次排序，还是数值分析厉害啊

Posted by a280920481 at 2018-12-27 14:55:40 on Problem 2976
```#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_N = 1005;

double p;

struct T
{
int a;
int b;
bool operator < (const T & y)
{
return (double)a - p * b > (double)y.a - p * y.b;
}
}t[MAX_N];

int n, k;

double C();

int main()
{
while (true)
{
cin >> n >> k;
if (!n)
{
break;
}

for (int i = 0; i < n; i++)
{
cin >> t[i].a;
}
for (int i = 0; i < n; i++)
{
cin >> t[i].b;
}
k = n - k;

p = 0.5;
double lp = 0.0;

while (p - lp > 0.0001 || lp - p > 0.0001)
{
lp = p;
p = C();
}

cout << (int)(100.0 * p + 0.5) << '\n';
}

return 0;
}

double C()
{
double x = 0.0, y = 0.0;

sort(t, t + n);

for (int i = 0; i < k; i++)
{
x += t[i].a;
y += t[i].b;
}

return x / y;
}
```

Followed by:

User ID:
Title:

Content: