(POJ) 3104 Drying

http://poj.org/problem?id=3104

首先，要先注意一下題目敘述：只有用散熱機(一次減k)，就不能風乾！！！

然後，答案具有單調性，而且似乎要用long long 存

於是，我們來列式：假設我們總共需要花id天，其中 j 天用散熱機， id - j 天用風乾，則：

a[x] - (id - j) - jk <= 0          -->    j >= (a[x] - id) / (k-1)

這裡要特別注意k=1的情況，要分case討論

於是乎，就AC啦XDDD

#include <iostream>

#include <stdio.h>

#include <algorithm>

#include <cstring>

using namespace std;

const int MAX_N = 100003;

long long int a[MAX_N];

long long int n,k;

bool check(long long int id) {

long long int ret=0;

for (int x=0;n>x;x++) {

if (a[x]<=id) continue;

else {

long long tmp=a[x];

if (k!=1) ret += (a[x]-id)/(k-1) + int(bool((a[x]-id)%(k-1)!=0));

else ret+=(a[x]-id);

}

// cout<<"x="<<x<<" ; ret = " <<ret<<endl;

}

// cout<<id<<" : "<<ret<<endl;

if (k==1&&ret>0)return false;

else if (k==1) return true;

if (id>=ret) return true;

else return false;

}

int main () {

while (scanf("%lld",&n) != EOF) {

for (int x=0;n>x;x++) scanf("%lld",&a[x]);

scanf("%lld",&k);

long long int l=0, r=450000000000000000;

while (r-l != 1) {

long long int mid=(l+r)/2;

if (check(mid)==true) r=mid;

else l=mid;

}

printf("%d\n",r);

}

}