本文最后更新于 719 天前,其中的信息可能已经有所发展或是发生改变。
Original Link
思想:
- 前缀和,双指针。
- 快指针
i
作为某一分割区间的右端点,慢指针 j
作为该区间的左端点;
- 当
a[i] - a[j + 1] >= m
时,需要将 j
右移,直到满足 a[i] - a[j] <= m
,
- 此时判断
a[i] - a[j]
的值,若满足 a[i] - a[j] == m
说明可以找到恰好等于所需价格的区间,并标记;
- 若
a[i] - a[j] >= m
说明不存在等于所需价格的解,此时需要维护最小接近的值 ans
。
代码:
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N = 1e6 + 3; |
| |
| typedef long long LL; |
| |
| LL a[N]; |
| |
| LL ans = 0x3f3f3f3f; |
| |
| void solve(){ |
| int n, m; cin >> n >> m; |
| for(int i = 1; i <= n; i ++){ |
| cin >> a[i]; a[i] += a[i - 1]; |
| } |
| bool flag = 0; |
| for(int i = 1, j = 0; i <= n; i ++){ |
| while(a[i] - a[j + 1] >= m && j < i) j ++; |
| if(a[i] - a[j] == m){ |
| cout << j + 1 << '-' << i << endl; |
| flag = 1; |
| } |
| else if(a[i] - a[j] > m) ans = min(ans, a[i] - a[j]); |
| } |
| if(!flag){ |
| for(int i = 1, j = 0; i <= n; i ++){ |
| while(a[i] - a[j + 1] >= m && j < i) j ++; |
| if(a[i] - a[j] == ans) cout << j + 1 << '-' << i << endl; |
| } |
| } |
| } |
| |
| int main(){ |
| solve(); |
| return 0; |
| } |