1611F - ATM and Students详细题解(*1800,线段树维护前缀和;双指针算法(思维))

简介: 1611F - ATM and Students详细题解(*1800,线段树维护前缀和;双指针算法(思维))

1611F - ATM and Students

题目大意:

给你一个数组a,找到最大连续段[ l , r ] [l,r][l,r]:

a l + a l + 1 + . . . + a r + s > = 0 al+al+1+...+ar+s>=0al+al+1+...+ar+s>=0 (条件1)

a l + a l + 1 + . . . + a r + s < 0 al+al+1+...+ar+s<0al+al+1+...+ar+s<0 (条件2)

或者l 到 n 都 满 足 a l + a l + 1 + . . . + a n + s > = 0 l到n都满足al+al+1+...+an+s>=0lnal+al+1+...+an+s>=0

如果找不到a l + a l + 1 + . . . + a r + s > = 0 al+al+1+...+ar+s>=0al+al+1+...+ar+s>=0,则输出-1。

1.双指针算法:

结论:如果a l + a l + 1 + . . . + a r − 1 + s > = 0 , al+al+1+...+ar-1+s>=0,al+al+1+...+ar1+s>=0a l + a l + 1 + . . . + a r + s < 0 al+al+1+...+ar+s<0al+al+1+...+ar+s<0,那么以l ll为左端点的满足条件一最大连续子段为:

[ l , r − 1 ] [l,r-1][l,r1],l ll对答案的贡献已经到头了!记录下来l , r l,rl,r

接下来

所以我们只需要将l ll的指针向右移一位:看看以l + 1 l+1l+1为左端点的区间[ l + 1 , r ] [l+1,r][l+1,r],是不是能满足条件1

1..如果能,以l + 1 l+1l+1为左端点移动 r rr 的指针向右找满足条件1最大位置,记录下来。

2.如果不能,继续移动左指针,找到满足条件一的即可,中间的那些点就算有右端点小于r的区间满足条件一,对答案的贡献也小于原先的区间[ l , r − 1 ] [l,r-1][l,r1],所以等于对答案没有贡献,直接跳过就行了

如果此时的左指针指向的数和右指针指向的数满足条件一,则往后移右指针更新答案。

代码如下:

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
# define rep(i,be,en) for(int i=be;i<=en;i++)
# define pre(i,be,en) for(int i=be;i>=en;i--)
typedef pair<int, int> PII;
#define ll long long
#define endl "\n"
#define LOCAL
#define pb push_back
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
ll qpow(int a, int b) {
  ll ans = 1;
  while (b) {
    if (b & 1) ans = ans * a;
    a = (ll)a * a;
    b >>= 1;
  }
  return ans;
}
inline int read()
{
  int X = 0;
  bool flag = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flag = 0;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    X = (X << 1) + (X << 3) + ch - '0';
    ch = getchar();
  }
  if (flag) return X;
  return ~(X - 1);
}
inline void write(int X)
{
  if (X < 0) {
    X = ~(X - 1);
    putchar('-');
  }
  if (X > 9) write(X / 10);
  putchar(X % 10 + '0');
}
//有效代码----------------------------------------------------------------------
int n, s;
ll a[N];
void solve()
{
  n = read();
  s = read();
  ll ans = 0;
  ll sum = s;
  int l = 0, r = 0;
  rep(i, 1, n)
  {
    a[i] = read();
  }
  int j = 1;
  for (int i = 1; i <= n; i++)
  {
    sum += a[i];
    while (j <= i && sum < 0)
    {
      sum -= a[j];
      j++;
    }
    if (sum >= 0)
    {
      if (ans < i - j + 1)
      {
        ans = i - j + 1;
        r = i;
        l = j;
      }
    }
  }
  if (l != 0 && r != 0)
  {
    printf("%d %d\n", l, r);
  } else
  {
    cout << -1 << endl;
  }
}
//有效代码-----------------------------------------------------------------------------
int main() {
  ios::sync_with_stdio;
  cin.tie(0);
  cout.tie(0);
  //#ifdef LOCAL
  //freopen("data.in.txt","r",stdin);
  //freopen("data.out.txt","w",stdout);
  //#endif
  int T = 1;
  scanf("%d", &T);
  while (T--)
  {
    solve();
  }
  return 0;
}

2.线段树写法

线段树维护区间[ l , r ] [l,r][l,r]的最小前缀和

如果[l,r]区间可行满足条件一,那么,向后找最大的满足条件的r(二分)

如果[l,r]区间不满足可行条件,l指针向左移,继续找答案

那么什么时候可行呢?

如果[l,r]区间的最小的前缀和sum[x] (x属于[l,r]),sum[x]-sum[l-1]+s>=0,那么这个区间[l,r]肯定满足sum[r]-sum[l-1]+s>=0,因为sum[r]>=sum[x],所以区间[l,r]满足条件一

如果sum[x]-sum[l-1]+s<0,那么[l,x]区间不满足条件一,那么[l,r]区间肯定也不满足,因为r>=x.

所以证明完毕,代码如下:

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
const LL INF = 1e15;
int n, s;
LL sum[N];
struct node
{
  int l;
  int r;
  LL p;
} tr[N << 2];
void build(int u, int l, int r)
{
  tr[u].l = l;
  tr[u].r = r;
  if (l == r)
  {
    tr[u].p = sum[l];//线段树维护前缀和
    return;
  }
  int mid = l + r >> 1;
  build(u << 1, l, mid);
  build(u << 1 | 1, mid + 1, r);
  tr[u].p = min(tr[u << 1].p, tr[u << 1 | 1].p);
}
LL query(int u, int l, int r) //找区间[l,r]的最小前缀和
{
  if (tr[u].l >= l && tr[u].r <= r)
  {
    return tr[u].p;
  }
  int mid = tr[u].r + tr[u].l >> 1;
  LL mi = 1e15;
  if (l <= mid) mi = min(query(u << 1, l, r), mi);
  if (r > mid) mi = min(query(u << 1 | 1, l, r), mi);
  return  mi;
}
bool check(int l, int r)
{
  if (query(1, l, r) - sum[l - 1] + s >= 0) return true;
  return false;
}
int main()
{
  int T;
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d%d", &n, &s);
    for (int i = 1; i <= n; i++)
    {
      int x;
      scanf("%d", &x);
      sum[i] = sum[i - 1] + x;
    }
    build(1, 1, n);
    int ans = 0;
    int ll = 0, rr = 0;
    for (int i = 1; i <= n; i++)
    {
      int l = i, r = n;
      while (l < r)//找最大的mid(r)
      {
        int mid = l + r + 1 >> 1;
        if (check(i, mid)) l = mid;
        else r = mid - 1;
      }
      if (check(i, l) && ans < (l - i + 1))//检查[i,l]区间是否合格
      {
        ans = l - i + 1;
        ll = i;
        rr = l;
      }
    }
    if (ans)
    {
      cout << ll << ' ' << rr << "\n";
    } else
    {
      cout << -1 << "\n";
    }
  }
  return 0;
}


目录
相关文章
|
3月前
|
算法 索引 容器
双指针算法详解
本文介绍了双指针算法及其应用。双指针算法是在数组或字符串中常用的高效技术,通过维护两个指针遍历数据结构以解决特定问题。根据指针移动方向,可分为同向双指针、相向双指针和快慢指针。同向双指针如移动零和复写零问题;快慢指针如快乐数问题;相向双指针如盛水最多的容器、有效三角形数量及多数之和等问题。通过合理运用双指针技巧,可简化代码并提高效率。
69 4
双指针算法详解
|
3月前
|
存储 算法 Java
前缀和算法
本文介绍了前缀和及其变种在解决区间求和问题中的应用。首先,一维前缀和可通过预处理数组快速求得任意区间的和。接着,二维前缀和扩展了这一思想,适用于矩阵操作。此外,文章探讨了如何利用前缀和解决诸如“寻找数组中心下标”、“除自身以外数组的乘积”等问题,并进一步讲解了涉及哈希表优化的“和为 K 的子数组”等相关题目。最后,通过实例展示了如何在矩阵中高效计算特定区域的元素之和。文中包含代码示例与图解说明,便于理解。
45 0
前缀和算法
|
2月前
|
人工智能 算法 C++
一篇带你速通前缀和算法(C/C++)
一篇带你速通前缀和算法(C/C++)
|
2月前
|
算法 C++
【算法】双指针+二分(C/C++
【算法】双指针+二分(C/C++
|
2月前
|
搜索推荐 C语言 C++
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
|
4月前
|
算法 C++
【算法】前缀和算法——和可被K整除的子数组
【算法】前缀和算法——和可被K整除的子数组
|
4月前
|
算法
【算法】前缀和算法——和为k的子数组之和
【算法】前缀和算法——和为k的子数组之和
|
4月前
|
算法
【算法】前缀和——除自身以外数组的乘积
【算法】前缀和——除自身以外数组的乘积
|
4月前
|
算法
【算法】前缀和——寻找数组的中心下标
【算法】前缀和——寻找数组的中心下标