Drying
Time Limit: 2000MS |
|
Memory Limit: 65536K |
Total Submissions: 5563 |
|
Accepted: 1428 |
Description
It is very hard to wash and especially to dry clothes in winter. But Jane is a very smart girl. She is not afraid of this boring process. Jane has decided to use a radiator to make drying faster. But the radiator is small, so it can hold only one thing at a time.
Jane wants to perform drying in the minimal possible time. She asked you to write a program that will calculate the minimal time for a given set of clothes.
There are n clothes Jane has just washed. Each of them took ai water during washing. Every minute the amount of water contained in each thing decreases by one (of course, only if the thing is not completely dry yet). When amount of water contained becomes zero the cloth becomes dry and is ready to be packed.
Every minute Jane can select one thing to dry on the radiator. The radiator is very hot, so the amount of water in this thing decreases by k this minute (but not less than zero — if the thing contains less than k water, the resulting amount of water will be zero).
The task is to minimize the total time of drying by means of using the radiator effectively. The drying process ends when all the clothes are dry.
Input
The first line contains a single integer n (1 ≤ n ≤ 100 000). The second line contains ai separated by spaces (1 ≤ ai ≤ 109). The third line contains k (1 ≤ k ≤ 109).
Output
Output a single integer — the minimal possible number of minutes required to dry all clothes.
Sample Input
sample input #1
3
2 3 9
5
sample input #2
3
2 3 6
5
Sample Output
sample output #1
3
sample output #2
2
Source
Source Code
Problem: 3104
|
|
User: bingshen
|
Memory: 536K |
|
Time: 610MS |
Language: C++ |
|
Result: Accepted
|
-
Source Code
#include<stdio.h>
int w[100005];
int maxi;
int n,k;
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
bool slove(int sum)
{
int i,j=0,tmp;
for(i=0;i<n;i++)
{
tmp=max(w[i]-sum,0);
if(!tmp)
continue;
else
{
j=j+tmp/(k-1);
if(tmp%(k-1))
j++;
if(j>sum)
return false;
}
}
return true;
}
int work()
{
int st=0,ed=maxi,mid;
while(st<=ed)
{
mid=((st+ed)>>1);
if(slove(mid))
ed=mid-1;
else
st=mid+1;
}
return st;
}
int main()
{
int i;
while(scanf("%d",&n)!=EOF)
{
maxi=-1;
for(i=0;i<n;i++)
{
scanf("%d",&w[i]);
if(w[i]>maxi)
maxi=w[i];
}
scanf("%d",&k);
if(k==1)
printf("%d/n",maxi);
else
printf("%d/n",work());
}
return 0;
}
分享到:
相关推荐
poj 3104,思想二分,二分天数,判断单调性,
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj题目分类 POJ(Princeton Online Judge)是一個在线编程平台,为编程爱好者和学生提供了大量的...这些知识点涵盖了算法、数据结构、数学、计算几何学等领域的多个方面,为编程爱好者和学生提供了广泛的知识基础。
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
北大POJ2002-Squares 解题报告+AC代码
北大POJ1159-Palindrome 解题报告+AC代码
poj题目,需要可以下载,虽然没有包含所有的题目,但是对初级入门有帮助
PKU 、POJ ACM/ICPC300多题的代码,还有各种典型问题的分类代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
Poj中一些题目的源代码,里面共有二十多道题目,OI
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ1048,加强版的约瑟夫问题 难度中等