首页 > 代码库 > bzoj 3043: IncDec Sequence

bzoj 3043: IncDec Sequence

2024-10-15 22:12:39   212人阅读

bzoj 3043: IncDec Sequence
差分 转化

题目大意：给定一个序列，提供一个操作：将某个区间内所有数+1或-1
求将所有数变成一样最少多少次操作，以及最终可以有多少种数

考虑差分后的序列
每次对[l,r]进行+1/-1，相当于在差分后的数组上对l进行+1/-1，然后对r+1进行-1/+1
特殊的，如果r=n，那么就相当于对l进行了+1/-1
我们最终的目标是将差分数组变成第一个位置是最终的数字，2~n都是0
那么我们统计差分后的数组的2~n号位置上每个位置上的数
令pos为所有正数的和，neg为所有负数的和的绝对值
那么首先是pos和neg对消 可能会剩下
剩下的有两种选择：自己消掉或者与1号位置对消
故第一问答案为max(pos,neg) 第二问答案为abs(pos-neg)+1


后面 的 1 的分配 与顺序是无关的 ，也就是说
自 自 1 与
1 自 自 在 本质上是相同的
然后本质不同的 只有 n+1 种 分别是 选 n 个自 n-1 个自.....1个自 以及 0 个自


其实我们还可以把他转化成 球盒问题
将 n个相同的球放入 2 个相同的盒子中 ， 允许空盒 ，求有几种方案
然后其实答案就是 n+1 第一个盒子放 0 个球 放1 个球 放 2 个球 ..... 放 n 个球

 

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iomanip>
 8 #include <iostream> 
 9 #define ll long long 
10 using namespace std ; 
11 
12 const int maxn = 100011 ;  
13 ll pos,neg,n ; 
14 ll a[maxn] ;  
15 
16 int main() 
17 {
18     scanf("%lld",&n) ;  
19     for(int i=1;i<=n;i++) scanf("%lld",&a[ i ]) ; 
20     for(int i=2;i<=n;i++) 
21     {
22         if(a[ i ] - a[ i-1 ] > 0 ) 
23             pos+=a[ i ] - a[ i-1 ] ; 
24         else
25             neg+=a[ i-1 ] -a[ i ] ;  
26     }
27     printf("%lld\n%lld\n",max(pos,neg),abs(pos-neg)+1) ; 
28     return 0 ; 
29 }

 

bzoj 3043: IncDec Sequence


联系
我们