读书人

求帮忙觅BUG

发布时间: 2013-07-16 22:38:05 作者: rapoo

求帮忙找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;
}


[解决办法]
请试以下输入:
1 1
0.01

printf("%d.%02d\n", p/100, p%100);
以上语句将输出:
0.00
而不是:
0.01

改为:
printf("%.2lf\n",(double)p/100.0);
可AC。

读书人网 >C++

热点推荐