[已解决]问题求解

ExiaGN001

51nod 2540 平分 (查无此题)
考虑足球比分系统，一场足球比赛从开始到结束的过程中，摄像机随机拍摄了n张比分信息，问你本场比赛最多出现了几次平分。
例如：3个比分信息为：
2 0
3 1
3 4
最终比分为3:4，所以最多只可能出现最初的0:0以及3:3这2次平分。如果只有1张3:4，那么最多可能有0:0 1:1 2:2 3:3共4次平分。

输入
第一行一个数n。
接下来n行，每行两个数a[ i],b[ i]，表示第i次拍摄时比分为a[ i]:b[ i]。
最后一次拍摄的比分即为最终比分。
n<=10000，a[ i],b[ i]<=10^9,a[ i],b[ i]保证不降。

输出
输出最多平分次数，包括开局的0:0。

输入样例
3
2 0
3 1
3 4
输出样例
2

模糊不清的官方题解：
给出的分数本身是有序的。为了简化思考，我们只考虑相邻的 2 个比分如何计数。
例如：从 2：5 到 8：10 ，可能出现的平分是 5:5,6:6,7:7,8:8 。 5=max(2,5),8=min(10,8) ，因此平分的数量是 min(a[ i],b[ i])-max(a[i-1],b[i-1])+1 。
但还存在另外一种情况，例如：从 2：5 到 3：6 ，其中不可能出现平分，也就是 min(a[ i],b[ i])-max(a[i-1],b[i-1])+1<0 的情况，这种情况下计数为 0 。
因此，我们可以推出一个 O(n) 的算法，统计最多可能的平分。

求C/C++解答！
(非水帖且有用回答会给予评分）
将在8月26日设置最佳答案

最佳答案

月排行榜 / 总排行榜

jhq999

2022-8-23 19:46:06

不知道对不对

1. int main()
   
2. {
   
3.         int n,i=0,j=0,bf1=0,bf2=0,count=0;
   
4.         scanf("%d",&n);
   
5.         //int (*bf)[2]=(int(*)[2])malloc(n,sizeof(int)*2);
   
6.         int minbf=0,maxbf=0;
   
7.         for(i=0;i<n;i+=1)
   
8.     {
   
9.         scanf("%d:%d",&bf1,&bf2);
   
10.         int m=bf1>bf2?bf2:bf1;
    
11.         if(m>=maxbf)
    
12.         {
    
13.             if(count)count+=m-maxbf+1;
    
14.             else
    
15.                 count=1;
    
16. 
    
17.         }
    
18.         maxbf=maxbf>bf1?maxbf:bf1;
    
19.         maxbf=maxbf>bf2?maxbf:bf2;
    
20. 
    
21.     }
    
22.     printf("%d\n",count);
    
23.         return 0;
    
24. }

复制代码

1. 2
   
2. 2:5 3:6
   
3. 1

复制代码

1. 3
   
2. 2:0
   
3. 3:1
   
4. 3:4
   
5. 2

复制代码

1. 2
   
2. 2:5
   
3. 8:10
   
4. 5

复制代码

跳转到最佳答案楼层

jhq999

不知道对不对

1. int main()
   
2. {
   
3.         int n,i=0,j=0,bf1=0,bf2=0,count=0;
   
4.         scanf("%d",&n);
   
5.         //int (*bf)[2]=(int(*)[2])malloc(n,sizeof(int)*2);
   
6.         int minbf=0,maxbf=0;
   
7.         for(i=0;i<n;i+=1)
   
8.     {
   
9.         scanf("%d:%d",&bf1,&bf2);
   
10.         int m=bf1>bf2?bf2:bf1;
    
11.         if(m>=maxbf)
    
12.         {
    
13.             if(count)count+=m-maxbf+1;
    
14.             else
    
15.                 count=1;
    
16. 
    
17.         }
    
18.         maxbf=maxbf>bf1?maxbf:bf1;
    
19.         maxbf=maxbf>bf2?maxbf:bf2;
    
20. 
    
21.     }
    
22.     printf("%d\n",count);
    
23.         return 0;
    
24. }

复制代码

1. 2
   
2. 2:5 3:6
   
3. 1

复制代码

1. 3
   
2. 2:0
   
3. 3:1
   
4. 3:4
   
5. 2

复制代码

1. 2
   
2. 2:5
   
3. 8:10
   
4. 5

复制代码

ExiaGN001

jhq999 发表于 2022-8-23 19:46
不知道对不对

感谢回复，但是还是与预期结果不符。
谢谢

编程追风梦

去度娘家里做客就好

ExiaGN001

编程追风梦 发表于 2022-8-24 10:25
去度娘家里做客就好

查过有用的话就不会来问了（悲