华师一附中OI组

标题: P1178 到天宫做客 [打印本页]
作者: admin    时间: 2018-5-11 17:23
标题: P1178 到天宫做客

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


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

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

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

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

作者: admin    时间: 2018-5-11 17:36
线段树统计当然可行但是有点大材小用，我们这里用一个很巧妙地方法， 把一年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++;

  28.     }

  30.     cout<<fixed<<setprecision(0)<<(s*24*60*60*1.0/366);  ///C++也有保留小数的函数 printf不是唯一
  31.     return 0;
  32. }
复制代码
作者: 倚窗倾听风吹雨    时间: 2018-7-4 10:38
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2