首页 > 代码库 > 2016.10.30 济南学习 Day2 下午 T1

2016.10.30 济南学习 Day2 下午 T1

【问题描述】

  一张长度为??的纸带,我们可以从左至右编号为0 ? ??(纸带最左端标号为 0)。现在有??次操作,每次将纸带沿着某个位置进行折叠,问所有操作之后纸带 的长度是多少。

【输入格式】

  第一行两个数字??, ??如题意所述。 接下来一行??个整数代表每次折叠的位置。

【输出格式】

   一行一个整数代表答案。

【样例输入】

  5 2 3 5

【样例输出】

  2

【样例解释】

   树上有只鸟。

【数据规模与约定】

  对于60%的数据,??, ?? ≤ 3000。 对于100%的数据,?? ≤ 1018 , ?? ≤ 3000。

 1 #include<iostream>
 2 #include<cstdio>
 3 #define ULL unsigned long long
 4 using namespace std;
 5 ULL f[3005],n,L,R;
 6 int m;
 7 inline ULL read()
 8 {
 9     ULL w=0,flag=1;char ch=getchar();
10     while(ch>9||ch<0){if(ch==-)flag=-1;ch=getchar();}
11     while(ch<=9&&ch>=0){w=w*10+ch-0;ch=getchar();}
12     return w*flag;
13 }
14 int main()
15 {
16     freopen("he.in","r",stdin);
17     freopen("he.out","w",stdout);
18     n=read();m=read();
19     L=0;R=n;
20     for(int i=1;i<=m;i++)f[i]=read();
21     for(int i=1;i<=m;i++)
22     {
23         
24         if(f[i]*2>=L+R) R=f[i];// 舍掉右边 
25         else L=f[i];//  舍掉左边 
26         
27         for(int j=i+1;j<=m;j++)
28         {
29             if(f[j]>R)    f[j]=R*2-f[j];
30             if(f[j]<L)    f[j]=L*2-f[j];
31         }
32         
33     }
34     
35     cout<<R-L<<endl;
36     fclose(stdin);
37     fclose(stdout);
38     return 0;
39 }

 

2016.10.30 济南学习 Day2 下午 T1