首页 > 代码库 > hdu 4928 Series 2 (优化+模拟)
hdu 4928 Series 2 (优化+模拟)
题意:
一个含n个数的序列a,每两个相邻的数相减得到一个新数,这些数组成一个新的序列。
如果所有得到的序列都满足非严格的单调性,则原序列为nice series;如果给出的序列
本来不满足单调性,它是ugly series。否则输出k,表示前k个序列都满足单调性,第k+1不满足。
算法:
模拟合并和判断单调性,如果不优化会Tle.
如果去掉前导0和后导0,因为0-0还是0,省去一部分操作。
但是为了避免得到的下一个序列的判断有误,应该前后各留一个0.
比如:
7
1 1 1 3 5 7 9
第一次变换得到 0 0 2 2 2 2 -->满足单调性
第二次 如果完全忽略前导0 则下一个序列变为 0 0 0
而实际上应该是 0 2 0 0 0不满足单调性
#include<cstdio> #include<iostream> #include<cstring> #define maxn 100010 using namespace std; typedef long long ll; ll a[maxn]; int main() { int T,n; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%I64d",&a[i]); int l = 1,r = n; int k = 0,f1,f2; for(int i=0;i<n;i++) { while(l<r && !a[l]) l++; if(l>1) //由于把前导0和后导0去掉了,可能会影响下一轮的判断 l = l-1; //所以前面留一个0 else l = 1; //本来就没有前导0 while(l<r && !a[r]) r--; if(r<n-i) r = r+1; //后面留一个0 else r = n-i; //本来就没有后导0 if(l>=r) break; f1 = f2 = 0; for(int d=l;d<r;d++) { if(a[d+1]>a[d]) //如果单调递增 f1 = 1; if(a[d+1]<a[d]) //如果单调递减 f2 = 1; } if(f1 && f2) //既有单调递增的段也有递减的部分,即不满足单调性 { if(k==0) printf("ugly series\n"); else printf("%d\n",k-1); break; } for(int j=l;j<r;j++) a[j]=a[j+1]-a[j]; r--; //得到下一个序列,个数减一 k++; } if(!f1 || !f2) printf("nice series\n"); } return 0; } /* 7 1 1 1 3 5 7 9 ans = 1 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。