求帮忙找BUG
POJ 1064: http://poj.org/problem?id=1064
二分查找的上限，按理说用 sum/k 就可以。但是会WA。改用_max则AC。
有点想不通原因，也可能是二分算法的问题？ 自己看不出来，求解答。谢谢。
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef unsigned char uint8;
typedef vector<int> ivec;
typedef set<int> iset;
#ifdef WIN32
typedef __int64 int64;
typedef unsigned __int64 uint64;
#else
typedef long long int64;
typedef unsigned long long uint64;
#endif
//#define DEBUG
#define MAX(a,b) ((a)>(b) ? (a) : (b))
#define MIN(a,b) ((a)<(b) ? (a) : (b))
inline bool DoubleEqual(double a, double b) {
const double e = 0.00001;
double c = a - b;
return c<e && c>-e;
}
static inline int imax(int a, int b) {
return a>b ? a : b;
}
static inline int imax(int a, int b, int c) {
return imax(imax(a,b), c);
}
static inline int imin(int a, int b) {
return a<b ? a : b;
}
static inline int imin(int a, int b, int c) {
return imin(imin(a,b), c);
}
///////////////////////////////////////////////////////////////////////
int64 stocks[10001];
int64 n,k;
bool Try(int64 size) {
int64 r = 0;
for(int64 i =0;i <n;i++) {
r += stocks[i]/size;
if(r>=k)
return true;
}
return false;
}
void P1064() {
scanf("%d %d", &n, &k);
char buf[32];
int64 sum = 0, _max = 0;
for(int64 i = 0; i < n; i ++) {
scanf("%s", buf);
int64 l = strlen(buf);
int64 tmp = atoi(buf + l - 2);
buf[l-3] = 0;
tmp += atoi(buf) * 100;
sum += tmp;
if( tmp > _max) _max = tmp;
stocks[i] = tmp;
}
int64 p = 1, q = sum/k, m;
while( p<=q ) {
m = (p+q)>>1;
if( Try(m) ) {
p = m + 1;
} else {
q = m - 1;
}
}
--p;
printf("%d.%02d\n", p/100, p%100);
}
///////////////////////////////////////////////////////////////////////
int main() {
P1064();
#ifdef WIN32
system("pause");
#endif
return 0;
}
