hdu 4193 - Non-negative Partial Sums(滚动数列)

本文主要是介绍hdu 4193 - Non-negative Partial Sums(滚动数列)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给定一个由n个整数组成的整数序列，可以滚动，滚动的意思就是前面k个数放到序列末尾去。问有几种滚动方法使得前面任意个数的和>=0.

思路：

先根据原来的数列求sum数组，找到最低点，然后再以最低点为始点，求解题目答案，（每求解一始点i，符合要求的条件为：sum[i]>=minx,[minx是i<x<=n中的最小值],之所以不用考虑前面的，就是因为我们的预处理是的所有的x<i的sum[x]的值满足sum[x]>=sum[i]）

代码如下：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>#define M 1000005
#define mod 1000000007
#define INF 0x7fffffff
#define eps 1e-8
#define LL long long
#define LLU unsigned long longusing namespace std;int a[M], n, mini;
LL sum[M], minx;
int main ()
{while(scanf("%d", &n) && n){minx = INF;sum[0] = 0;for(int i= 1; i <= n; ++i){scanf("%d", &a[i]);sum[i] = sum[i-1]+a[i];if(minx>sum[i]){minx = sum[i];mini = i;}}sum[0] = 0;int c = 0;for(int i = mini+1; i <= n; ++i)sum[++c] = sum[c-1]+a[i];for(int i = 1; i <= mini; ++i)sum[++c] = sum[c-1]+a[i];minx = sum[n];int ans = 0;for(int i = n-1; i >= 0; --i){if(sum[i]<=minx){ans += 1;minx = sum[i];}}printf("%d\n", ans);}return 0;
}

单调队列的思路是比较简单的，

就是确定一个始点以后，然后在队列中找最小的值，满足要求的条件为：minx-sum[i]>=0

代码如下：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>#define M 1000005
#define mod 1000000007
#define INF 0x7fffffff
#define eps 1e-8
#define LL long long
#define LLU unsigned long longusing namespace std;
int n, head, rear, a[M];
LL sum[2*M], deq[2*M];
void insert(int x)
{while(head<=rear && sum[deq[rear]]>=sum[x]) --rear;deq[++rear] = x;
}
LL push(int x)
{while(deq[head]<=x-n) ++head;return sum[deq[head]];
}
int main ()
{while(scanf("%d", &n) && n){head = 1; rear = 0;for(int i = 1; i <= n; ++i)scanf("%d", &a[i]);sum[0] = 0;for(int i = 1; i <= n; ++i)sum[i] = sum[i-1]+a[i];for(int i = n+1; i <= 2*n; ++i)sum[i] = sum[i-1]+a[i-n];for(int i = 1; i < n; ++i)insert(i);int ans = 0;for(int i = n; i < 2*n; ++i){insert(i);if(push(i)-sum[i-n]>=0) ++ans;}printf("%d\n", ans);}return 0;
}

这篇关于hdu 4193 - Non-negative Partial Sums(滚动数列)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---