Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 二分WA的童鞋注意一下写法

Posted by Onlynagesha at 2017-11-23 17:01:28 on Problem 3111 and last updated at 2017-11-23 17:01:39
```正确的写法：
void solve()
{
double left = 0.0;
double right = 0.0;
for (int i = 0; i < N; i++)
right = max(right, 1.0 * value[i] / weight[i]);

while (1)
{
double mid = (left + right) / 2.0;
for (int i = 0; i < N; i++)
{
item[i].idx = i + 1;
item[i].prior = value[i] - mid * weight[i];
}
sort(item, item + N);

double sum = 0.0;
for (int i = 0; i < K; i++)
sum += item[N - K + i].prior;

if (sum >= 0.0)
{
left = mid;
if (right - left < 1e-7)
break; //跳出二分时需要保证运行结果是可行解
}
else
right = mid;
}

sort(item + N - K, item + N, cmpIdx);

for (int i = 0; i < K; i++)
printf("%d ", item[N - K + i].idx);
}

（跳出二分时，item数组中存储的可能不是可行解）
void solve()
{
double left = 0.0;
double right = 0.0;
for (int i = 0; i < N; i++)
right = max(right, 1.0 * value[i] / weight[i]);

while (right - left >= 1e-7)
{
double mid = (left + right) / 2.0;
for (int i = 0; i < N; i++)
{
item[i].idx = i + 1;
item[i].prior = value[i] - mid * weight[i];
}
sort(item, item + N);

double sum = 0.0;
for (int i = 0; i < K; i++)
sum += item[N - K + i].prior;

if (sum >= 0.0)
left = mid;
else
right = mid;
}

sort(item + N - K, item + N, cmpIdx);

for (int i = 0; i < K; i++)
printf("%d ", item[N - K + i].idx);
}```

Followed by: