P1178 到天宫做客

admin

https://www.luogu.org/problemnew/show/P1178


题目描述
有一天，我做了个梦，梦见我很荣幸的接到了猪八戒的邀请，到天宫陪他吃酒。我犹豫了。天上一日，人间一年啊！当然，我是个闲人，一年之中也没有多少时日是必须在人间的，因此，我希望选一个最长的空闲时间段，使我在天上待的时间尽量长。记住，今年是4000年。天上一天也是24小时，每小时60分，每分60秒。

输入输出格式
输入格式：
输入文件的第一行是一个非负整数 N，表示4000年中必须呆在人间的天数，以下共N行，每行两个用空格隔开的正整数，即日期（月,日），输入文件保证无错误，日期无重复。

输出格式：
输出文件仅有一行包含一个非负整数，即在天上的时间(四舍五入精确到秒)。

输入输出样例
输入样例#1：
2
3 8
12 2
输出样例#1：
63266

倚窗倾听风吹雨

1. #include<iostream>
   
2. #include<cmath>
   
3. #include<iomanip>
   
4. using namespace std;
   
5. int i,j,n,b,c,day;
   
6. double s,maxs=0,p,k;
   
7. bool a[367]={};
   
8. char data[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
   
9. int main()
   
10. {
    
11.     cin>>n;
    
12.     for(i=1;i<=n;i++)
    
13.     {
    
14.         day=0;
    
15.         cin>>b>>c;
    
16.         for(j=1;j<b;j++)
    
17.             day+=data[j];
    
18.         day+=c;
    
19.         a[day]=1;
    
20.     }
    
21.     for(i=1;i<=366;i++)
    
22.     {
    
23.         if(a[i]==1)s=0;
    
24.         else s++;
    
25.         if(s>maxs)maxs=s;
    
26.     }
    
27.     k=maxs/366*3600*24;
    
28.     cout<<fixed<<setprecision(0)<<k;
    
29.     return 0;
    
30. }
    

复制代码

admin

线段树统计当然可行但是有点大材小用，我们这里用一个很巧妙地方法， 把一年366天摆在纸上，需要在人间的天上就插上标记，看看那个段最长就是，也就是我那50道题里面讲的 最长平台统计。

1. #include<iostream>
   
2. #include<iomanip>
   
3. using namespace std;
   
4. double y1;
   
5. long long n,m,d,sum,s,l,i;
   
6. int md[13]= {0,31,29,31,30,31,30,31,31,30,31,30,31};
   
7. int w[400];
   
8. int main()
   
9. {
   
10.     cin>>n;
    
11.     for(i=1; i<=n; i++)
    
12.     {
    
13.         cin>>m>>d;
    
14.         sum=d;for (int j=1; j<=m-1; j++ )sum+=md[j];  ///统计这一天是今年的第几天
    
15.         w[sum]=1; ///置位标记
    
16.     }
    
17.     w[0]=w[367]=1;  ///首尾假岗哨
    
18.     l=s=0;
    
19.     for(i=0; i<=367; i++)
    
20.     {
    
21.         if(w[i]==1)
    
22.         {
    
23.             if(l>s)s=l;
    
24.             l=0;
    
25.         }
    
26.         else l++;
    
27. 
    
28.     }
    
29. 
    
30.     cout<<fixed<<setprecision(0)<<(s*24*60*60*1.0/366);  ///C++也有保留小数的函数 printf不是唯一
    
31.     return 0;
    
32. }
    

复制代码