| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贴份不动点迭代法代码,复杂度接近O(n*logn),几乎只要常数次排序,还是数值分析厉害啊#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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator