有N个人在AMT机前,ATM机内有S元,
每个人会存Ai元或者取-Ai元,取决于Ai的正负号。
当ATM机钱不够下个人的时候就会关闭。
请你选择一个连续的区间,使得ATM机能服务最多的人。
很明显,找一个最长的连续区间使得区间和 sum + S >= 0 。
利用双指针来维护区间,时间复杂度是On的。
将每个头指针都延展到能延展的最大长度即可。记尾指针。
更新答案,并且将这个头指针往前,并将头指针值d出。
再用记忆了的尾指针继续往后探。
这样每个点最多被访问2次。
上次写过类似的,这次还是没写出来,太菜了。
AC代码#include//#include //priority_queue #define PII pair #define ll long long using namespace std; const int INF = 0x3f3f3f3f; const int N = 200010 ; long long a[N] ; long long sum[N] ; int main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int T ; cin >> T ; while (T--) { int n ; long long s; cin >> n >> s ; int ma = 0 ; int q = 0 , z = 0 ; for (int i = 1 ; i <= n ; i++ ) cin >> a[i] ; long long tmp = s ; for (int i = 1 , j = 1 ; i <= n ; i++ ) { while ( j <= n && tmp + a[j] >= 0 ) { tmp += a[j] ; j++ ; if ( ma < j - i ) { ma = j - i ; q = i ; z = j-1 ; } } tmp -= a[i] ; } if ( ma == 0 ) cout << "-1n" ; else { cout << q << " " << z << "n" ; } } return 0 ; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)