今年暑假不AC——(优化贪心+快排)

2/22/2017来源:ASP.NET技巧人气:1282

think: 1今晚终于AC道题目了…..这道题目感觉和贪心里面的区间区间覆盖问题类似,只不过感觉这道题目明显需要优化子问题,因为有可能出现像【0, 7】,【1, 3】, 【3, 6】这样的区间,不能因为先出现一个条件判断了,之前自己做的区间覆盖问题好像没有想的这么深,看来之前自己区间覆盖问题的AC有点水…,不过现在想明白了也很幸运 2回归题目,题目可以建立两个结构体数组,存储各个节目开始的时间和结束的时间,然后用快排函数将输入的按照开始时间升序排序,同一开始时间则按照结束时间升序排序,然后将最优子问题存储在另一个结构数组中,需要注意的是第一个存储和最后一个存储,我用存储的结构数组是从下标为1开始存储的,这样可以减少第一个存储的判断条件,融合了动态规划思想的最优子问题将贪心进行优化

sdut题目链接 hdoj原题链接

今年暑假不AC Time Limit: 1000MS Memory Limit: 65535KB

PRoblem Description “今年暑假不AC?” “是的。” “那你干什么呢?” “看世界杯呀,笨蛋!” “@#$%^&*%…” 确实如此,世界杯来了,球迷的节日也来了,估计很多ACMer也会抛开电脑,奔向电视了。 作为球迷,一定想看尽量多的完整的比赛,当然,作为新时代的好青年,你一定还会看一些其它的节目,比如新闻联播(永远不要忘记关心国家大事)、非常6+7、超级女生,以及王小丫的《开心辞典》等等,假设你已经知道了所有你喜欢看的电视节目的转播时间表,你会合理安排吗?(目标是能看尽量多的完整节目)

Input 输入数据包含多个测试实例,每个测试实例的第一行只有一个整数n(n<=100),表示你喜欢看的节目的总数,然后是n行数据,每行包括两个数据Ti_s,Ti_e (1<=i<=n),分别表示第i个节目的开始和结束时间,为了简化问题,每个时间都用一个正整数表示。n=0表示输入结束,不做处理。

Output 对于每个测试实例,输出能完整看到的电视节目的个数,每个测试实例的输出占一行。

Example Input 12 1 3 3 4 0 7 3 8 15 19 15 20 10 15 8 18 6 12 5 10 4 14 2 9 0

Example Output 5

Hint hdoj2037

Author hdojACM程序设计期末考试

以下为accepted代码

#include <stdio.h> #include <stdlib.h> struct node { int first; int end; }ans[104], jk[104]; int flag; int cmp(const void *a, const void *b) { struct node *c = (struct node *)a; struct node *d = (struct node *)b; if(c->first != d->first) { return (c->first - d->first); } else return (c->end - d->end); } int main() { int n, i; while(scanf("%d", &n) && n) { flag = 0; for(i = 0; i < n; i++) { scanf("%d %d", &ans[i].first, &ans[i].end); } qsort(&ans[0], n, sizeof(ans[0]), cmp); /*for(i = 0; i < n; i++) { printf("%d %d\n", ans[i].first, ans[i].end); }*/ ///jk[0] = ans[0]; jk[0].first = 0, jk[0].end = 0; for(i = 0; i < n; i++) { if(i != n-1) { if(jk[flag].end <= ans[i].first && ans[i].end <= ans[i+1].end) { jk[++flag] = ans[i]; } } else { if(jk[flag].end <= ans[i].first) { jk[++flag] = ans[i]; } } } printf("%d\n", flag); } return 0; } /*************************************************** User name: Result: Accepted Take time: 0ms Take Memory: 108KB Submit time: 2017-02-18 20:56:16 ****************************************************/