1、二分
poj 2018 Best Cow Fences
? http://poj.org/problem?id=2018
? 题意：给定一个正整数数列??，求一个平均数最大的长度不小于?? 的子段。
? 二分答案（平均值）
? 判定是否存在一个长度不小于?? 的子段，平均数不小于二分的值??
? 判定方法：
? 把数列中每个数都减去平均值，问题变为是否存在长度不小于?? 的子段，子段和非负
?转化为前缀和相减的形式?????? ?? ? min 0≤??≤????? ?????? ?? ≥ 0
1 #include<iostream> 2 #include<string> 3 #include<cmath> 4 #include<cstring> 5 #include<cstdio> 6 #include<map> 7 #include<stack> 8 #include<queue> 9 #include<algorithm> 10 #define maxn 100005 11 using namespace std; 12 13 inline int read() 14 { 15 char c=getchar(); 16 int res=0,x=1; 17 while(c<‘0‘||c>‘9‘) 18 { 19 if(c==‘-‘) 20 x=-1; 21 c=getchar(); 22 } 23 while(c>=‘0‘&&c<=‘9‘) 24 { 25 res=res*10+(c-‘0‘); 26 c=getchar(); 27 } 28 return x*res; 29 } 30 31 int n,m; 32 double l=100000000,r=0; 33 double a[maxn],b[maxn],c[maxn]; 34 35 bool check(double x) 36 { 37 double temp=0,ans=-1000000; 38 for(int i=1;i<=n;i++) 39 { 40 b[i]=a[i]-x; 41 c[i]=c[i-1]+b[i]; 42 } 43 for(int i=m;i<=n;i++) 44 { 45 temp=min(temp,c[i-m]); 46 ans=max(ans,c[i]-temp); 47 } 48 if(ans>=0) return 1; 49 else return 0; 50 } 51 52 int main() 53 { 54 n=read();m=read(); 55 for(int i=1;i<=n;i++) 56 { 57 scanf("%lf",&a[i]); 58 l=min(l,a[i]); 59 r=max(r,a[i]); 60 } 61 while(r-l>0.00001) 62 { 63 double mid=(l+r)/2; 64 if(check(mid)) 65 { 66 l=mid; 67 } 68 else 69 { 70 r=mid; 71 } 72 } 73 cout<<(int)(r*1000)<<endl; 74 return 0; 75 }
2、双指针扫描
? Subsequence http://poj.org/problem?id=3061
? 给定序列 ?? 和一个整数 ??，求一个长度最小的连续子段，使得子段和 ≥ ??。
? 前缀和+ 二分 O （??log??）
? 双指针扫描 O （?? ）——枚举左端 ??，所求的子段右端 ?? 是单调递增的
前缀和+ 二分 O ??log??：
1 #include<iostream> 2 #include<string> 3 #include<cmath> 4 #include<cstring> 5 #include<cstdio> 6 #include<map> 7 #include<stack> 8 #include<queue> 9 #include<algorithm> 10 #define maxn 100005 11 using namespace std; 12 13 inline int read() 14 { 15 char c=getchar(); 16 int res=0,x=1; 17 while(c<‘0‘||c>‘9‘) 18 { 19 if(c==‘-‘) 20 x=-1; 21 c=getchar(); 22 } 23 while(c>=‘0‘&&c<=‘9‘) 24 { 25 res=res*10+(c-‘0‘); 26 c=getchar(); 27 } 28 return x*res; 29 } 30 31 int t,n,m,l,r,aa; 32 int a[maxn],b[maxn]; 33 34 bool check(int x) 35 { 36 int ans=0; 37 for(int i=x;i<=n;i++) 38 { 39 ans=max(ans,b[i]-b[i-x]); 40 } 41 if(ans>=m) return 1; 42 else return 0; 43 } 44 45 int main() 46 { 47 t=read(); 48 while(t--) 49 { 50 n=read();m=read(); 51 for(int i=1;i<=n;i++) 52 { 53 aa=read(); 54 a[i]=aa; 55 b[i]=b[i-1]+a[i]; 56 } 57 if(b[n]<m) 58 { 59 printf("0\n"); 60 continue; 61 } 62 l=1;r=n; 63 while(l<=r) 64 { 65 int mid=(l+r)>>1; 66 if(check(mid)) 67 { 68 r=mid-1; 69 } 70 else 71 { 72 l=mid+1; 73 } 74 } 75 printf("%d\n",l); 76 } 77 return 0; 78 }
双指针扫描：
1 #include<iostream> 2 #include<string> 3 #include<cmath> 4 #include<cstring> 5 #include<cstdio> 6 #include<map> 7 #include<stack> 8 #include<queue> 9 #include<algorithm> 10 #define maxn 100005 11 using namespace std; 12 13 inline int read() 14 { 15 char c=getchar(); 16 int res=0,x=1; 17 while(c<‘0‘||c>‘9‘) 18 { 19 if(c==‘-‘) 20 x=-1; 21 c=getchar(); 22 } 23 while(c>=‘0‘&&c<=‘9‘) 24 { 25 res=res*10+(c-‘0‘); 26 c=getchar(); 27 } 28 return x*res; 29 } 30 31 int t,n,m,aa,ans; 32 int a1,a2,pd; 33 int a[maxn],b[maxn]; 34 35 int main() 36 { 37 t=read(); 38 while(t--) 39 { 40 n=read();m=read(); 41 ans=1000000; 42 memset(a,0,sizeof(a)); 43 memset(b,0,sizeof(b)); 44 for(int i=1;i<=n;i++) 45 { 46 aa=read(); 47 a[i]=aa; 48 b[i]=b[i-1]+a[i]; 49 } 50 if(b[n]<m) 51 { 52 printf("0\n"); 53 continue; 54 } 55 for(int i=1;i<=n;i++) 56 { 57 if(a[i]>=m) 58 { 59 printf("1\n"); 60 pd=1; 61 break; 62 } 63 } 64 if(pd==1) 65 { 66 pd=0; 67 continue; 68 } 69 a1=1;a2=1; 70 while(a1<=n&&a2<=n) 71 { 72 if(b[a2]-b[a1-1]>=m) 73 { 74 ans=min(ans,a2-a1+1); 75 a1++; 76 } 77 else 78 { 79 a2++; 80 } 81 } 82 printf("%d\n",ans); 83 } 84 return 0; 85 }
? Costume Party http://poj.org/problem?id=3663
? 给定序列 ?? 和一个整数 ??，求有多少对 ??,?? 满足 ???? + ???? ≤ ??。
? 把序列 ?? 排序
? 枚举 ??，满足要求的 ?? 的右端位置是单调递减的
双指针扫描：一个指针指向第一个元素，另一个指向最后一个元素，然后向中间间移动指针并累加个数。
1 #include<iostream> 2 #include<string> 3 #include<cmath> 4 #include<cstring> 5 #include<cstdio> 6 #include<map> 7 #include<stack> 8 #include<queue> 9 #include<algorithm> 10 #define maxn 20005 11 using namespace std; 12 13 inline int read() 14 { 15 char c=getchar(); 16 int res=0,x=1; 17 while(c<‘0‘||c>‘9‘) 18 { 19 if(c==‘-‘) 20 x=-1; 21 c=getchar(); 22 } 23 while(c>=‘0‘&&c<=‘9‘) 24 { 25 res=res*10+(c-‘0‘); 26 c=getchar(); 27 } 28 return x*res; 29 } 30 31 int n,m,a1,a2,ans,aa; 32 int a[maxn]; 33 34 int main() 35 { 36 n=read();m=read(); 37 for(int i=1;i<=n;i++) 38 { 39 aa=read(); 40 a[i]=aa; 41 } 42 sort(a+1,a+1+n); 43 a1=1;a2=n; 44 while(a1<a2) 45 { 46 if(a[a1]+a[a2]<=m) 47 { 48 ans+=a2-a1; 49 a1++; 50 } 51 else 52 { 53 a2--; 54 } 55 } 56 cout<<ans; 57 return 0; 58 }
二分做法：先排序，再枚举 i ∈ [1,n-1] ，二分查找第一个j使得a[i]+a[j]<=s,然后ans+=j-i；
1 #include<iostream> 2 #include<string> 3 #include<cmath> 4 #include<cstring> 5 #include<cstdio> 6 #include<map> 7 #include<stack> 8 #include<queue> 9 #include<algorithm> 10 #define maxn 1000005 11 using namespace std; 12 13 inline int read() 14 { 15 char c=getchar(); 16 int res=0,x=1; 17 while(c<‘0‘||c>‘9‘) 18 { 19 if(c==‘-‘) 20 x=-1; 21 c=getchar(); 22 } 23 while(c>=‘0‘&&c<=‘9‘) 24 { 25 res=res*10+(c-‘0‘); 26 c=getchar(); 27 } 28 return x*res; 29 } 30 31 int n,m,aa; 32 long long ans; 33 int a[maxn]; 34 35 int main() 36 { 37 n=read();m=read(); 38 for(int i=1;i<=n;i++) 39 { 40 aa=read(); 41 a[i]=aa; 42 } 43 sort(a+1,a+1+n); 44 for(int i=1;i<n;i++) 45 { 46 int l=i+1,r=n; 47 while(l<=r) 48 { 49 int mid=(l+r)>>1; 50 if(a[i]+a[mid]<=m) 51 { 52 l=mid+1; 53 } 54 else 55 { 56 r=mid-1; 57 } 58 } 59 ans+=(long long)r-i; 60 } 61 cout<<ans; 62 return 0; 63 }
3、前缀和与差分
前缀和：
? 对于一个给定的数列A，它的前缀和数列S是通过递推能求出的基本信息之一：
? ??[??] = σ??=1 ?? ??[??]
? 一个部分和，即数列A中某个下标区间内的数的和，可以表示为前缀和相减的形式：
? sum ??,?? = σ??=?? ?? ?? ?? = ?? ?? ? ??[?? ? 1]
? 在二维数组（矩阵）中，也有类似的递推形式，可求出二维前缀和，进一步计算出二维 部分和。
差分：
? 长度为 ?? 的序列 ?? 的差分序列是一个长度为?? 的序列 ??
? 其中 ??1 = ??1，???? = ???? ? ?????1 2 ≤ ?? ≤ ??
? 差分序列 ?? 的前缀和数组就是原序列??
? 把 ?? 的区间 [??,??] 加 ??，?? 的变化为：???? 加 ??，????+1 减 ??
输入格式：
输入文件名为input.txt
输入文件的第一行为正整数n和正整数R，接下来的n行每行有3个正整数，分别表示 xi，yi ，vi 。
输出格式：
输出文件名为output.txt
输出文件仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过32767）。
2 1
0 0 1
1 1 1
1
先预处理出矩阵的二维前缀和，然后枚举选用矩阵的右下角，利用二维前缀和公式，
统计最大值，由于矩阵的边缘不能取，注意一下边界，可以将给定矩阵长和宽各减一。
1 #include<iostream> 2 #include<string> 3 #include<cmath> 4 #include<cstring> 5 #include<cstdio> 6 #include<map> 7 #include<stack> 8 #include<queue> 9 #include<algorithm> 10 #define maxn 5505 11 using namespace std; 12 13 inline int read() 14 { 15 char c=getchar(); 16 int res=0,x=1; 17 while(c<‘0‘||c>‘9‘) 18 { 19 if(c==‘-‘) 20 x=-1; 21 c=getchar(); 22 } 23 while(c>=‘0‘&&c<=‘9‘) 24 { 25 res=res*10+(c-‘0‘); 26 c=getchar(); 27 } 28 return x*res; 29 } 30 31 int n,m,h,x; 32 int aa,bb,cc; 33 int ju[maxn][maxn]; 34 int ans; 35 36 int main() 37 { 38 n=read();m=read(); 39 for(int i=1;i<=n;i++) 40 { 41 aa=read();bb=read();cc=read(); 42 aa++;bb++; 43 ju[aa][bb]+=cc; 44 } 45 for(int i=1;i<=5001;i++) 46 { 47 for(int j=1;j<=5001;j++) 48 { 49 ju[i][j]+=ju[i-1][j]+ju[i][j-1]-ju[i-1][j-1]; 50 } 51 } 52 for(int i=m;i<=5001;i++) 53 { 54 for(int j=m;j<=5001;j++) 55 { 56 ans=max(ans,ju[i][j]-ju[i-m][j]-ju[i][j-m]+ju[i-m][j-m]); 57 } 58 } 59 cout<<ans; 60 return 0; 61 }
给定一个长度为n的数列a1?,a2?,?,an?，每次可以选择一个区间[l,r]，使这个区间内的数都加1或者都减1。
请问至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。
第一行一个正整数n
接下来n行,每行一个整数,第i+1行的整数表示ai。
第一行输出最少操作次数
第二行输出最终能得到多少种结果
4
1
1
2
2
1
2
对于100%的数据，n≤100000,0≤ai≤2147483648
首先维护一个差分序列，我们可以发现，如果修改区间[i,j]，那么在差分序列上只会修改i和j+1的值，
并且i和j+1的操作相反，由于我们最终要让差分序列变成全0序列，所以我们要优先考虑正负数互相抵消的情况，
也就是说我们让正数减去1，让负数加上1，这样我们一定会向目标靠近一步，最后我们在单独处理剩余的正数或者负数，所以说，进行的操作总是就是差分
序列中正数和与负数和的绝对值的最大值。至于第二问，由于正负数抵消的环节是必不可少的，所以我们只考虑单独处理的这一阶段，由于差分序列是同号的，
所以这个差分序列的原序列一定是单调的，所以可以从前往后操作，也可以从后往前操作，这样得出的结果就是正数和与负数和之差的绝对值+1；
1 #include<iostream> 2 #include<string> 3 #include<cmath> 4 #include<cstring> 5 #include<cstdio> 6 #include<map> 7 #include<stack> 8 #include<queue> 9 #include<algorithm> 10 #define maxn 100005 11 using namespace std; 12 13 inline int read() 14 { 15 char c=getchar(); 16 int res=0,x=1; 17 while(c<‘0‘||c>‘9‘) 18 { 19 if(c==‘-‘) 20 x=-1; 21 c=getchar(); 22 } 23 while(c>=‘0‘&&c<=‘9‘) 24 { 25 res=res*10+(c-‘0‘); 26 c=getchar(); 27 } 28 return x*res; 29 } 30 31 long long a1,a2; 32 long long n,aa,ans1,ans2; 33 int a[maxn],b[maxn]; 34 35 int main() 36 { 37 n=read(); 38 for(int i=1;i<=n;i++) 39 { 40 aa=read(); 41 a[i]=aa; 42 b[i]=a[i]-a[i-1]; 43 } 44 for(int i=2;i<=n;i++) 45 { 46 if(b[i]<0) 47 ans1+=b[i]*(-1); 48 if(b[i]>0) 49 ans2+=b[i]; 50 } 51 a1=max(ans1,ans2); 52 cout<<a1<<endl; 53 cout<<abs(ans1-ans2)+1; 54 return 0; 55 }
? 有N 头牛站成一行。两头牛能够相互看见，当且仅当它们中间的牛身高都比它们矮。
? 我们只知道其中最高的牛是第P 头，它的身高是H，不知道剩余 ?? ? 1 头牛的身高。
? 我们还知道M 对关系，每对关系都指明了某两头牛???? 和 ???? 可以相互看见。
? 求每头牛的身高最大可能是多少。
? 1 ≤ ??,?? ≤ 104，1 ≤ ?? ≤ 106
? 建立一个数组??，数组中起初全为0。
? 若一条关系指明???? 和 ???? 可以互相看见（不妨设???? < ????），则把数组?? 中下标为 ???? + 1 到 ???? ? 1 的数都减去1，意思是在???? 和 ???? 中间的牛，身高至少要比它们小1。
? 由于第P头牛是最高的，所以最终 ??[??] 一定为0，第 ?? 头牛的身高就等于?? + ??[??]。
? 可转化为建立一个数组??，对于每对 ???? 和 ????，令 ??[???? + 1] 减去1，??[????] 加上1。
? 其含义是：“身高减小1”的影响从???? + 1 开始，持续到???? ? 1，在 ???? 结束。
? 最后，?? 就等于 ?? 的前缀和。
注意一下，由于这道题的输入数据有重复，所以要去重。方法很简单，开一个map由pair映射到bool判断一下就行了。
1 #include<iostream> 2 #include<string> 3 #include<cmath> 4 #include<cstring> 5 #include<cstdio> 6 #include<map> 7 #include<stack> 8 #include<queue> 9 #include<algorithm> 10 #include<set> 11 #define maxn 10005 12 using namespace std; 13 14 inline int read() 15 { 16 char c=getchar(); 17 int res=0,x=1; 18 while(c<‘0‘||c>‘9‘) 19 { 20 if(c==‘-‘) 21 x=-1; 22 c=getchar(); 23 } 24 while(c>=‘0‘&&c<=‘9‘) 25 { 26 res=res*10+(c-‘0‘); 27 c=getchar(); 28 } 29 return x*res; 30 } 31 32 int n,p,m,h,aa,bb; 33 int a[maxn],b[maxn]; 34 map<pair<int,int>,bool>s; 35 36 int main() 37 { 38 n=read();p=read();h=read();m=read(); 39 for(int i=1;i<=n;i++) 40 { 41 a[i]=h; 42 b[i]=a[i]-a[i-1]; 43 } 44 for(int i=1;i<=m;i++) 45 { 46 aa=read();bb=read(); 47 if(s[make_pair(aa,bb)]) continue; 48 s[make_pair(aa,bb)]=1; 49 if(aa>bb) 50 swap(aa,bb); 51 b[aa+1]--; 52 b[bb]++; 53 } 54 for(int i=1;i<=n;i++) 55 { 56 b[i]=b[i-1]+b[i]; 57 printf("%d\n",b[i]); 58 } 59 return 0; 60 }
原文：https://www.cnblogs.com/snowy2002/p/10339727.html