合并数列（双指针 ）
思路解析
基本思路：
首先我们观察样例 这题需要我们输出满足要求的最小合并次数
那么我们得明确两件事情：
- 1.对于给定的这两个数列 A B 他们俩是一定可以通过若干次合并 变成我们想要的数列
也就说sum_A=sum_B 最坏情况下就是大不了合并所有数字 - 2.这个合并操作一定是单调增加的
什么意思 就是说 我们一定是越合并越大的 - 其次我们可以借助双指针的一个思想 分别在各自两个数列上游走
核心就是 保证元素一一对应相等 遇到不相等的我们就停下来进行操作
一开始都指向第一个元素 我们进行比较
如果一样 那么我们两个指针都往后继续走
如果不一样 那么肯定是一个大一个小 假设p指向大的 q指向小的 这样的话 我们想让p变的和q一样大
所以一定是让这个比较小的往后去合并
本质上就是为了让p q 两个指针指向的数值相等 - 如果保证这个方法的正确性呢？
那么不妨假设现在 pq两指针都指向数列中央的元素 前面都是我们合并好的 这时又发生了失配问题 如果往前面合并 会发生什么？
是不是就是会破坏我们前面合并的结果 无形之中就会增大我们最后结果的合并次数 所以一定是向后合并时最优的
AC代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int a[N],b[N];
int cnt;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<m;i++)
{
cin>>b[i];
}
int p=0;
int q=0;
while(p<n && q<m)
{
if(a[p]==b[q])
{
p++;
q++;
}else if(a[p]<b[q]) //p指向的元素较小需要向后去合并
{
p++;
a[p]+=a[p-1];//此时q是不用移动的
cnt++;
}else if(a[p]>b[q])
{
q++;
b[q]+=b[q-1];
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}
抓娃娃（思维+二分）
思路解析
AC代码
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
const int N = 1e5 + 10;
int n, m;
int main()
{
cin >> n >> m;
vector<pii>a(n);
vector<double>b(m);
for(int i = 0; i < n; i ++) {
int L, R; cin >> L >> R;
double mid = (L + R) / 2.0;
b[i] = mid;
}
for(int i = 0; i < m; i ++) {
cin >> a[i].x >> a[i].y;
}
sort(b.begin(), b.end());
auto check1 = [&](int mid, int i) {
return b[mid] >= a[i].x;
};
auto check2 = [&](int mid, int i) {
return b[mid] <= a[i].y;
};
for(int i = 0; i < m; i ++) {
int L = a[i].x, R = a[i].y;
int l1 = 0, r1 = n - 1;
while(l1 < r1) {
int mid = l1 + r1 >> 1;
if(check1(mid, i))
r1 = mid;
else
l1 = mid + 1;
}
int l2 = 0, r2 = n - 1;
while(l2 < r2) {
int mid = l2 + r2 + 1 >> 1;
if(check2(mid, i))
l2 = mid;
else
r2 = mid - 1;
}
if(b[l1] >= L && b[l2] <= R) {
cout << l2 - l1 + 1 << endl;
}else{
cout << 0 << endl;
}
}
return 0;
}
和与乘积（前缀和与双指针）
思路解析
- 题目解读：
首先这题的题意非常明了 就是让你找到满足区间元素之和正好等于该区间元素之积的区间个数 - 思考：
如果我们想要直接暴力来做 也就是说 分别求出该数列的前缀和和前缀积 再利用双指针的思想找到满足要求的区间
这显然是不合适的 首先不提时间复杂度 我们求前缀积这个操作就是不可取的 - 为什么不可取呢？
因为n最大可以取到2e5 每个数a最大也可以取到2e5
也就是说最坏的情况2e5个2e5相乘 不管是int 还是longlong 都是存不下的 大概可能存100个就爆掉了
但是即便这个方法是不可取的 也给我们了一个启示
就是说 加法相对于乘法它的增长速度是较慢的
我们如果要保证这个区间里面 区间和=区间积
那么一定是包含多个1的 - 举个例子： 2 5 1 1 1
就拿这个数列来举例 我们一旦出现了2*5 那么就相当于这个区间积就处在10的位置去等我们的区间和
而此时我们的区间和是7 所以显然 【1,5】就是满足要求的 - 基本思路：
在一般情况下
我们会找到一个整体 左右两端都是非1的数 我们以这个整体为中心 向左右两端延伸
延伸到再次出现非1的的数 假设左边1的长度为x x=min{我们需要的1的个数，左边有的1的个数} 右边也是同理
那么我们需要多少个1呢？
假设这个整体的积是 mup 这个整体的和是 sum 那么我们就需要mup-sum个1 ==
此时这个问题就转化成了一个滑动窗口的问题==
我们需要去维护这个窗口 去保证 在移动的过程中 窗口里面1的个数始终是我们想要的
*/
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll a[N], s[N], b[N], id[N];
ll l[N], r[N];
int n;
int cnt;
ll ans;
int main(){
cin >> n;
// 前缀和
for(int i = 1; i <= n; i ++){
cin >> a[i];
s[i] = s[i - 1] + a[i];
if(a[i] != 1){
cnt++;
b[cnt] = a[i];
id[cnt] = i;
} else {
ans++;
}
}
// 双指针
for(int i = 1, j = 2; i <= n; i ++) {
while(j <= n && a[j] == 1){
j ++;
}
r[i] = j - (i + 1);
if(j == i + 1) j ++;
}
for(int i = n, j = n - 1; i >=0; i --) {
while(j >= 1 && a[j] == 1){
j --;
}
l[i] = (i - 1) - j;
if(j == i - 1) j --;
}
ll maxv = s[n];
for(int i = 1; i <= cnt; i ++) {
ll c = 1;
for(int j = i; j <= cnt; j ++) {
c *= b[j];
if(c > maxv) break;
int lid = id[i];
int rid = id[j];
ll sum = s[rid] - s[lid - 1];
ll dis = c - sum;
if(dis == 0) {
ans ++;
} else if(dis > 0 && l[lid] + r[rid] >= dis) {
ll x = min(dis, l[lid]);
ll y = min(dis, r[rid]);
ans += (x + y - dis + 1);
}
}
}
cout << ans << endl;
return 0;
}