首页 > 代码库 > 济南学习D2T1__折纸带
济南学习D2T1__折纸带
他
【问题描述】
一张长度为n的纸带,我们可以从左至右编号为0 ?n(纸带最左端标号为
0) 。现在有m次操作,每次将纸带沿着某个位置进行折叠,问所有操作之后纸带
的长度是多少。
【输入格式】
第一行两个数字n,m如题意所述。
接下来一行m个整数代表每次折叠的位置。
【输出格式】
一行一个整数代表答案。
【样例输入】
5 2
3 5
【样例输出】
2
【样例解释】
树上有只鸟。
【数据规模与约定】
60%的数据,n,m ≤ 3000。
对于100%的数据,n≤ 10 18 ,m ≤ 3000。
_____________________________________________________________________________
题意很简单,主要就是更改以后折的点,60分可以用并查集维护,100更简单,读入所有的折点,暴力更改m2.
做题中出了点小问题,CENA测试时,我用的lld,忘了这个版本用I64d,笨啊!!!!!!!!!
_____________________________________________________________________________
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 5 using namespace std; 6 long long n,m; 7 long long sz[3010]; 8 long long l,r; 9 int main() 10 { 11 freopen("he.in","r",stdin); 12 freopen("he.out","w",stdout); 13 scanf("%I64d%I64d",&n,&m); 14 l=0;r=n; 15 for(long long i=0;i<m;i++)scanf("%I64d",sz+i); 16 for(long long i=0;i<m;i++) 17 { 18 long long dn=sz[i]; 19 if(r-dn>dn-l) 20 { 21 for(long long j=i+1;j<m;j++) 22 { 23 if(sz[j]>=l&&sz[j]<dn) 24 { 25 sz[j]=dn-sz[j]+dn; 26 } 27 } 28 l=dn; 29 } 30 else 31 { 32 for(long long j=i+1;j<m;j++) 33 { 34 if(sz[j]>dn&&sz[j]<=r) 35 { 36 sz[j]=dn-sz[j]+dn; 37 } 38 } 39 r=dn; 40 } 41 } 42 cout<<r-l<<endl; 43 fclose(stdin); 44 fclose(stdout); 45 return 0; 46 }
济南学习D2T1__折纸带
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。