大家好,又见面了,我是你们的朋友全栈君。
Description “今年暑假不AC?” “是的。” “那你干什么呢?” “看世界杯呀,笨蛋!” “@#$%^&*%...” 确实如此,世界杯来了,球迷的节日也来了,估计很多ACMer也会抛开电脑,奔向电视了。 作为球迷,一定想看尽量多的完整的比赛,当然,作为新时代的好青年,你一定还会看一些其它的节目,比如新闻联播(永远不要忘记关心国家大事)、非常6+7、超级女生,以及王小丫的《开心辞典》等等,假设你已经知道了所有你喜欢看的电视节目的转播时间表,你会合理安排吗?(目标是能看尽量多的完整节目) Input 输入数据包含多个测试实例,每个测试实例的第一行只有一个整数n(n<=100),表示你喜欢看的节目的总数,然后是n行数据,每行包括两个数据Ti_s,Ti_e (1<=i<=n),分别表示第i个节目的开始和结束时间,为了简化问题,每个时间都用一个正整数表示。n=0表示输入结束,不做处理。 Output 对于每个测试实例,输出能完整看到的电视节目的个数,每个测试实例的输出占一行。 Sample 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 Sample Output 5
#include<stdio.h> int main() { int a[100],b[100],i,j,n,c,d,ans,k; while(scanf("%d",&n)&&n) { for(i=0;i<n;i++) scanf("%d%d",&a[i],&b[i]); for(i=1;i<n;i++) //冒泡排序,在对数组b排序的同时,把相应的数组a也要对应排序 { for(j=0;j<n-i;j++) { if(b[j]>b[j+1]) { c=b[j]; d=a[j]; b[j]=b[j+1]; a[j]=a[j+1]; b[j+1]=c; a[j+1]=d; } } } ans=1; //表示已经看了第一个电视节目 k=b[0]; for(i=0;i<n-1;i++) //当结束时间小于等于开始时间,那么就可以看此时的电视节目,ans++ { for(j=i+1;j<n;j++) { if(k<=a[j]) {i=j-1; k=b[j]; ans++; } } } printf("%d\n",ans); } return 0; }
思路:想要看的电视越多,那么电视结束的时间就要越早=>数组b从小到大排序,从而对应的数组a也要排序;在算ans时还要注意结束时间与下一个开始时间
转载于:https://www.cnblogs.com/liufei-/p/9362567.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107388.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...