| ||||||||||
| 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 | |||||||||
提供一个非二分做法(附代码)// 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator