Отримання знань

дистанційна підтримка освіти школярів


Владелец кабеля
http://acm.pku.edu.cn/JudgeOnline/problem?id=1064

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на Pascal:

program PKU1064;
{$S-,Q-,R-,I-}

const maxn = 10001;

type integer = longint;

var n, m, l, r: integer;
a: array[1..maxn] of integer;

procedure prepare;
var i: integer;
j: double;
begin
read(n, m); r := 1;
for i := 1 to n do begin
read(j);
a[i] := round(j * 100);
if a[i] > r then r := a[i];
end;
end;

function calc(c: integer): integer;
var k, i: integer;
begin
if c = 0 then calc := m + 1 else begin
k := 0;
for i := 1 to n do begin
k := k + a[i] div c;
if k >= m then break;
end;
calc := k;
end;
end;

procedure main;
var mid: integer;
begin
l := 0;
while l < r do begin
mid := (l + r + 1) shr 1;
if calc(mid) >= m then l := mid else r := mid - 1;
end;
writeln(l / 100:1:2);
end;

begin
prepare;
main;
end.

   Пример решения на C++:

#include "iostream"
using namespace std;
int n,k;
int a[10100];
bool check(int mid)
{
int sum=0,i;
if(mid==0)return 0;
for(i=1; i <= n; ++i)
{
   sum+=a[i]/mid;
   if(sum >= k)return 1;
}
return 0;
}
int erfen(int MIN,int MAX)
{
int mid;
while(MIN <= MAX)
{
   mid=(MIN+MAX)/2;
   if(check(mid))
   { MIN=mid+1; }
   else
    MAX=mid-1;
}
return MAX;
}
int main()
{
int max,i;
double num,ans;
while(scanf("%d%d",&n,&k)!=EOF)
{
   max=0;
   for(i=1; i <= n; ++i)
   {
    scanf("%lf",&num);
    a[i]=(int)(100*num+0.3);
    if(max<a[i])max=a[i];
   }
   ans=double(erfen(1,max))/100;
    printf("%.2lf\n",ans);
}
return 0;
}
 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)