Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator