sco_1 2021-09-05 21:44 采纳率: 0%
浏览 42
已结题

贪心算法在使用归并排序出现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就可以了

    评论

报告相同问题?

问题事件

  • 系统已结题 9月13日
  • 创建了问题 9月5日

悬赏问题

  • ¥15 Matlab怎么求解含参的二重积分?
  • ¥15 苹果手机突然连不上wifi了?
  • ¥15 cgictest.cgi文件无法访问
  • ¥20 删除和修改功能无法调用
  • ¥15 kafka topic 所有分副本数修改
  • ¥15 小程序中fit格式等运动数据文件怎样实现可视化?(包含心率信息))
  • ¥15 如何利用mmdetection3d中的get_flops.py文件计算fcos3d方法的flops?
  • ¥40 串口调试助手打开串口后,keil5的代码就停止了
  • ¥15 电脑最近经常蓝屏,求大家看看哪的问题
  • ¥60 高价有偿求java辅导。工程量较大,价格你定,联系确定辅导后将采纳你的答案。希望能给出完整详细代码,并能解释回答我关于代码的疑问疑问,代码要求如下,联系我会发文档