hdu 3233 다운로드 관리자 (아 날로 그 문제)
제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=3233
제목: 일부 파일 을 다운로드 해 야 합 니 다. 지금 은 파일 의 크기 와 다운로드 한 백분율 을 제시 하고 일정한 다운로드 순서에 따라 마지막 으로 모든 파일 을 다운로드 하 는 데 필요 한 시간 을 구 합 니 다.다운로드 규칙 은 작은 파일 을 우선 다운로드 하고 크기 가 같은 파일 이 있 으 면 100% 많은 파일 을 우선 다운로드 하 는 것 입 니 다.
분석: 우선 규칙 에 따라 정렬 한 다음 에 m 길이 의 배열 을 유지 하고 이 파일 의 남 은 바 이 트 를 기록 할 수 있 습 니 다. 매번 바이트 가 가장 적은 파일 줄 이 누적 되 는 데 걸 리 는 시간 을 다운로드 한 다음 에 다운로드 하고 있 는 m - 1 개의 파일 의 바 이 트 를 업데이트 하고 모든 파일 을 다운로드 할 때 까지 마지막 누적 시간 은 출력 결과 입 니 다.
참조 코드:
#include
#include
#include
#include
#include
using namespace std;
const double eps = 1e-7;
struct node{
node(){}
node(double _size,double _rem):size(_size),rem(_rem){}
double size,rem;
};
node Q[1005],data[20005];
bool cmp(node a,node b)
{
if(fabs(a.size-b.size) < eps) return a.rem > b.rem;
return a.size < b.size;
}
double solve(int n,int m,double b)
{
int len = 0;
double ans = 0;
for(int i = 0;i < n;++i)
{
if(len < m)
{
double Size = data[i].size*(1-data[i].rem*0.01);
if(fabs(Size) < eps) continue;
Q[len++] = node(Size,0.0);
for(int j = len-1;j > 0;--j)
{
if(Q[j].size < Q[j-1].size)
swap(Q[j],Q[j-1]);
else
break;
}
}
if(len == m)
{
double t = Q[0].size / (b / m),s = Q[0].size;
ans += t;
for(int j = 1;j < len;++j)
{
Q[j].size -= s;
Q[j-1] = Q[j];
}
len--;
}
}
for(int i = 0;i < len;++i)
{
double t = Q[i].size / (b / (len-i)),s = Q[i].size;
ans += t;
for(int j = i;j < len;++j)
Q[j].size -= s;
}
return ans;
}
int main()
{
int n,m,b,casenum = 1;
while(scanf("%d%d%d",&n,&m,&b) && n+m+b)
{
for(int i = 0;i < n;++i)
scanf("%lf%lf",&data[i].size,&data[i].rem);
sort(data,data+n,cmp);
printf("Case %d: %.2lf
",casenum++,solve(n,m,(double)b));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.