POJ--3104

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 a_i 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 a_i separated by spaces (1 ≤ a_i ≤ 10⁹). The third line contains k (1 ≤ k ≤ 10⁹).

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

题目大意：

给你n件衣服，这些衣服都带有自己的水分，其中每分钟自然蒸发1滴水。你有一个小型烘干机，你可可以选择一件衣服用烘干机

一分钟内吹掉k滴水，当然烘干机每分钟只能对一件衣服进行操作。

输入：

第一行 n，接下来n个数a1,a2,a3,a4......an 分别代表衣服的水分，然后一个数k表示烘干机一分钟内吹k滴水。

题意也可以这样理解，所有衣服每分钟减少1滴水分，每分钟可以选择一件衣服额外减少(k-1)滴水。

这题乍看贪心，实则二分。（因为一般的贪心会超时）

这n件衣服中，设水分最大的衣服含的水分为max, 所以答案一定在0到max之间。

l=0， r=max;

枚举中间值mid=(l+r)/2，每件衣服先减去mid的水分，额外的水分用烘干机吹干，所用时间为t，

若t<=mid证明答案在mid或者mid的左边。

t>mid证明答案在mid 的右边

就这样每次减半------ - - - - - - - - - - - - - - 直至 l=r出答案

此题注意以下几点

1.开long long int会爆

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define N 100100
#define INF 0x3f3f3f3f
using namespace std;
long long  a[N];
int main()
{
    long long n,k,l,r,mid,maxx,t;
    while(~scanf("%lld",&n))
    {
        maxx=-1;
        for(int i=0; i<n; i++)
        {
            scanf("%lld",&a[i]);
            maxx=maxx>a[i]?maxx:a[i];
        }
        scanf("%lld",&k);
        l=0,r=maxx;
        if(k==1)//k=1对下面的情况不易判断，所以在此特判
        {
            printf("%lld
",maxx);
            continue;
        }
        while(r!=l)
        {
            t=0;
            mid=(r+l)/2;
            for(int i=0; i<n; i++)
            {
                if(a[i]>mid)
                {
                    t+=(a[i]-mid)/(k-1);
                    if((a[i]-mid)%(k-1)!=0)
                        t++;
                }
            }
            if(t<=mid)
                r=mid;
            else
                l=mid+1;
        }
        cout<<l<<endl;
    }
    return 0;
}