首页 > 代码库 > 蚯蚓——在做了一个星期的水题之后,又和这个题目耗了一会(其实好像奶牛和连棋也是水题,只是上上个星期不想写解体报告)

蚯蚓——在做了一个星期的水题之后,又和这个题目耗了一会(其实好像奶牛和连棋也是水题,只是上上个星期不想写解体报告)

  NOIP2017 Day2 第二题。先写了一两个中午思路混乱的版本,后来理清楚了做法重新打了一遍,却因为没有发现cmp 写反而又多花了几天时间。

  最终如下。

技术分享
 1 #include<queue>
 2 #include<cstdio>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 const int N=7166666;
 7 int n,m,q,u,v,t;
 8 int q1[N],q2[N],q3[N],head1=0,head2=0,head3=0,tail1=0,tail2=0,tail3=0;
 9 bool cmp(int l,int r){return l>r;}
10 int main(){
11     cin>>n>>m>>q>>u>>v>>t;
12     for(int i=1;i<=n;i++)cin>>q1[tail1++];
13     sort(q1,q1+tail1,cmp);
14     for(int i=1;i<=m;i++){
15         int lth;
16         if(head1<tail1&&
17         (q1[head1]>=q2[head2]||head2>=tail2)&&
18         (q1[head1]>=q3[head3]||head3>=tail3))
19             lth=q1[head1++];
20         else if(head2<tail2&&
21         (q2[head2]>=q1[head1]||head1>=tail1)&&
22         (q2[head2]>=q3[head3]||head3>=tail3))
23             lth=q2[head2++];
24         else lth=q3[head3++];
25         lth+=(i-1)*q;
26         if(i%t==0)cout<<lth<<" ";
27         int nx1=(long long)lth*u/v,nx2=lth-(long long)lth*u/v;
28         q2[tail2++]=nx1-q*i;
29         q3[tail3++]=nx2-q*i;
30     }
31     cout<<endl;
32     for(int i=1;i<=n+m;i++){
33         int lth;
34         if(head1<tail1&&
35         (q1[head1]>=q2[head2]||head2>=tail2)&&
36         (q1[head1]>=q3[head3]||head3>=tail3))
37             lth=q1[head1++];
38         else if(head2<tail2&&
39         (q2[head2]>=q1[head1]||head1>=tail1)&&
40         (q2[head2]>=q3[head3]||head3>=tail3))
41             lth=q2[head2++];
42         else lth=q3[head3++];
43         lth+=q*m;
44         if(i%t==0)cout<<lth<<" ";
45     }
46     return 0;
47 }
Method_01

  这次是先在本地上用cena 测了成功,但是因为机子慢而且正式测评有O2 所以时限给自己开了三秒。最终本地有两三个点一秒到两秒,洛谷上总耗时2113ms.

蚯蚓——在做了一个星期的水题之后,又和这个题目耗了一会(其实好像奶牛和连棋也是水题,只是上上个星期不想写解体报告)