sco_1
2021-09-05 21:44
采纳率: 0%
浏览 15

贪心算法在使用归并排序出现RE

小张经常为了事情太多安排不开而苦恼。现在他手头有 n 项任务,每项任务都有一个开始时间 s_i 和结束时间 e_i 。要想完成一个任务必须从开始时间做到结束时间,并且同一时间小张只能进行一项任务。
小张想知道他最多可以完成几项任务。
Input
第一行一个整数 n(1 \leq n \leq 300000 ) ,表示小张手头任务的个数。

接下来 n 行,每行两个整数 s_i,e_i(1 \leq s_i < e_i \leq 10^9 ) ,表示任务的开始时间和结束时间。

Output
一行一个整数,表示小张最多可以完成几项任务。
问题貌似在ver_count里面:


#include <stdio.h>
#include <stdlib.h>
int ans=0;
int start[300030],end[300030];


void ver_count(int a[],int b[],int l,int m,int r)
{
    int k=0,i=l,j=m+1;
    
    int *temp1 = (int *)malloc((r-l+1)*sizeof(int)),*temp2 = (int *)malloc((r-l+1)*sizeof(int));
    
    while (i <= m && j <= r)
        {
            if(b[i]<=b[j])
                {
                    temp2[k]=b[i];
                    temp1[k]=a[i];
                    k++;i++;
                    
                }
            else
                {
                    temp2[k]=b[j];
                    temp1[k]=a[j];
                    k++;j++;
                }
        }
    while(i<=m)
    {
        temp2[k]=b[i];
        temp1[k]=a[i];
        k++;i++;
    }
    while(j<=r)
    {
        temp1[k]=a[j];
        temp2[k]=b[j];
        k++;j++;
    }
    for(int s=0;s<k;s++)
    {
        a[l+s]=temp1[s];
        b[l+s]=temp2[s];
    }
    free(temp1);
    free(temp2);
    

}

void merge(int a[],int b[],int left,int right)
{
    if(left==right) return;
    
    int middle=(left+right)/2;
    merge(a, b, left, middle);
    merge(a, b, middle+1, right);
    ver_count(a, b, left, middle, right);
    
}
int main()
{
    int n=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d %d",&start[i],&end[i]);
    }
    merge(start, end, 0, n-1);

    int *p=NULL,*q=NULL,flag=1;
    p=end;q=start+1;
    while((p<=end+n-1)&&(q<=start+n))
    {
        if(*p<=*q)
        {
            ans++;
            p+=flag;q++;
            flag=1;
        }
        else {
            q++;
            flag++;
        }
            
    }
    printf("%d\n",ans+1);
    
    return 0;
}

  • 收藏

1条回答 默认 最新

  • sco_1 2021-09-05 21:52

    用static就可以了

    打赏 评论

相关推荐 更多相似问题