Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator