2016.10.30 济南学习 Day2 下午 T1

时间：2025-02-06 10:36:50

他

【问题描述】

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

【输入格式】

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

【输出格式】

　　 一行一个整数代表答案。

【样例输入】

　　5 2

　　3 5

【样例输出】

　　2

【样例解释】

　　 树上有只鸟。

【数据规模与约定】

　　对于60%的数据，N, M ≤ 3000。 对于100%的数据，N ≤ 10^18 , M ≤ 3000。

 #include<iostream>

 #include<cstdio>

 #define ULL unsigned long long

 using namespace std;

 ULL f[],n,L,R;

 int m;

 inline ULL read()

 {

     ULL w=,flag=;char ch=getchar();

     while(ch>''||ch<''){if(ch=='-')flag=-;ch=getchar();}

     while(ch<=''&&ch>=''){w=w*+ch-'';ch=getchar();}

     return w*flag;

 }

 int main()

 {

     freopen("he.in","r",stdin);

     freopen("he.out","w",stdout);

     n=read();m=read();

     L=;R=n;

     for(int i=;i<=m;i++)f[i]=read();

     for(int i=;i<=m;i++)

     {

         if(f[i]*>=L+R) R=f[i];// 舍掉右边

         else L=f[i];//  舍掉左边 

         for(int j=i+;j<=m;j++)

         {

             if(f[j]>R)    f[j]=R*-f[j];

             if(f[j]<L)    f[j]=L*-f[j];

         }

     }

     cout<<R-L<<endl;

     fclose(stdin);

     fclose(stdout);

     return ;

 }

思路：对于每次折叠，从该点划分成两半，舍掉长度短的一半，并且维护一次后面所有的折叠点

相关文章