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

提供一个非二分做法(附代码)

Posted by PvbeLLN at 2024-05-03 12:03:05 on Problem 1877
// Problem: 洪水! Flooded!
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/UVA815
// Create Time: 2024-03-19 22:48:21

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
/*================*/

inline int read()
{
	char c=getchar();int x=0,f=1;
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=x*10+c-48;
	return x*f;
}

#define r(a) (a)=read()

const double eee=1e-7;
int T,m,n,tot,nowtot,cnt,cntt;
double ans;
int map[1000],add[1000];

void print()
{
	printf("Water level is %.2f meters.\n",ans+eee);
	printf("%.2f percent of the region is under water.\n\n",(double)(100.0*cntt/(m*n)+eee));
}

int chk(double a)
{
	cnt=0;
	for (int i=1;i<=m*n;i++)
	{
		if (a>map[i]) cnt++;
	}
	return cnt;
}

signed main()
{
	while (1)
	{
		r(m);r(n);
		if (m==0&&n==0) return 0;
		T++;
		printf("Region %d\n",T);
		memset(map,0,sizeof(map));
		memset(add,0,sizeof(add));
		for (int i=1;i<=m*n;i++) r(map[i]);
		r(tot);
		sort(map+1,map+m*n+1);
		for (int i=1;i<=m*n;i++) add[i]=add[i-1]+map[i]*100;
		for (int i=1;i<=m*n;i++)
		{
			nowtot=tot+add[i];
			ans=(double)nowtot/(100*i);
			cntt=chk(ans);
			if (cntt==i)
			{
				print();
				break;
			}
		}
	}
	return 0;
}

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