qq_23908539 2015-09-30 11:20 采纳率: 87.5%
浏览 2428

贪心的一个经典问题,,,

图片说明
输入

第1行:1个数N,线段的数量(2 <= N <= 10000)
第2 - N + 1行:每行2个数,线段的起点和终点(-10^9 <= S,E <= 10^9)

输出

输出最多可以选择的线段数量。

输入示例

3
1 5
2 3
3 6

输出示例

2

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef struct {
    long long tb;
    long long te;
} TIME;
TIME TIME_TABLE[10007];
bool cmp(TIME a,TIME b) 
{
    return (a.te < b.te);
}
int N;

int main()
{   
    int cnt;
    int ans;
    while(~scanf("%d",&N))
    {
        if(N == 0) break;
        //默认的ans是1 
        ans = 1;
        cnt = 0;
        //将存放时间的数组排序 
        for(int i = 0;i < N;i++) 
            scanf("%ld%ld",&TIME_TABLE[i].tb,&TIME_TABLE[i].te);
        sort(TIME_TABLE,TIME_TABLE+N,cmp);

        for(int i = 1;i < N;i++) {
        //如果有序数组(按照结束时间从小到大排序)
        //的第i项的开始时间比目前选定的一项(cnt)的结束时间要晚 
        //那么就把它当做下一个cnt,然后ans计数加一 
            if(TIME_TABLE[i].tb >= TIME_TABLE[cnt].te) {
                cnt = i;
                ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
} 

结果最后是WA。。各位大神帮忙看看

  • 写回答

1条回答 默认 最新

  • longint64 2015-10-01 13:47
    关注

    ~scanf("%d",&N)是什么意思?这不是取反吗?
    读入成功了返回值是true,然后取反,成立false,于是直接不进入函数。至少我觉得是这样的。
    蒟蒻走过。。。
    另外,楼上我可以咬吗?(这才是我想说的关键)

    评论

报告相同问题?

悬赏问题

  • ¥30 这是哪个作者做的宝宝起名网站
  • ¥60 版本过低apk如何修改可以兼容新的安卓系统
  • ¥25 由IPR导致的DRIVER_POWER_STATE_FAILURE蓝屏
  • ¥50 有数据,怎么建立模型求影响全要素生产率的因素
  • ¥50 有数据,怎么用matlab求全要素生产率
  • ¥15 TI的insta-spin例程
  • ¥15 完成下列问题完成下列问题
  • ¥15 C#算法问题, 不知道怎么处理这个数据的转换
  • ¥15 YoloV5 第三方库的版本对照问题
  • ¥15 请完成下列相关问题!