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