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

## 刚串完门回来～用堆排序完全没有问题～我试过了，sort和堆都可以～（附代码）

Posted by Moon_1st at 2011-02-03 09:29:22 on Problem 3663
In Reply To:求解释：为什么用堆排序会wa?难道有特殊数据？ Posted by:gaozhenyangzhou at 2011-02-02 22:49:50
```堆方法的实现如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 20010;

int n, s, len[N];

void heap(int x, int y)
{
int i, j, tmp = len[x];
i = x;
j = i << 1;
while(j <= y)
{
if(j<y && len[j]<len[j+1]) j++;
if(len[j] > tmp)
{
len[i] = len[j];
i = j;
j = i << 1;
}
else  break;
}
len[i] = tmp;
}

int deal(int l, int r, int tmp)
{
int req = -1, mid, pre = l-1;
if(l > r)  return 0;
while(l <= r)
{
mid = (l+r) >> 1;
if(len[mid] <= tmp)
{
req = mid;
l = mid + 1;
}
else  r = mid - 1;
}
if(req == -1)  return 0;
else  return req-pre;
}

int main()
{
int i, ls, ans = 0;
scanf("%d%d", &n, &s);
for(i = 1; i <= n; i++)  scanf("%d", &len[i]);
for(i = n/2; i > 0; i--)  heap(i, n);
ls = n;
for(i = 1; i < n; i++)
{
swap(len[1], len[ls--]);
heap(1, ls);
}
for(i = 1; i <= n; i++)
ans += deal(i+1, n, s-len[i]);
printf("%d\n", ans);
return 0;
}```

Followed by: