`
java-mans
  • 浏览: 11344159 次
文章分类
社区版块
存档分类
最新评论

HDU 3415 Max Sum of Max-K-sub-sequence(单调队列)

 
阅读更多
/*AC
思路:使用sum[i]存储前i个序列之和,队列中存储区间内出现过最小序列和,这样只需要sum[i]前去最小序列和即可。
*/
#include <iostream>
using namespace std;
const int nMax = 100010;
const int INF = 0x7fffffff;
int A[nMax];
int sum[2 * nMax];//这里需要增倍
struct Queue
{
	int pos;
	int v;
	Queue(){}
	Queue(int pos, int v): pos(pos), v(v){}
}queue[2 * nMax];
int front, rear;
int t, n, k;
int main()
{
	//freopen("e://data.txt", "r", stdin);
	scanf("%d", &t);
	while(t --)
	{
		scanf("%d%d", &n, &k);
		sum[0] = 0;
		for(int i = 1; i <= n; ++ i)
		{
			scanf("%d", &A[i]);
			sum[i] = sum[i - 1] + A[i];
		}
		for(int i = n + 1; i <= n + k; ++ i)
			sum[i] = sum[i - 1] + A[i - n];
		front = rear = 0;
		int Max = -INF;
		int l, r;
		queue[front ++] = Queue(0, 0);//队列中存储最小元素和
		for(int i = 1; i <= n + k; ++ i)
		{
			while(rear < front && (i - queue[rear].pos) > k)//这里做了改动
				rear ++;
			if(sum[i] - queue[rear].v > Max)//把结果运算放到了前面,这样更好一些
			{
				Max = sum[i] - queue[rear].v;
				l = queue[rear].pos + 1;
				r = i;
			}
			while(rear < front && queue[front - 1].v > sum[i])
				front --;
			queue[front ++] = Queue(i, sum[i]);
			
		}
		printf("%d %d %d\n", Max, (l - 1) % n + 1, (r - 1) % n + 1);
	}
	return 0;
}


/*AC
错误出在①处
#include <iostream>
using namespace std;
const int nMax = 100010;
int A[nMax];
int sum[2 * nMax];//这里需要增倍
struct Queue
{
	int pos;
	int v;
	Queue(){}
	Queue(int pos, int v): pos(pos), v(v){}
}queue[2 * nMax];
int front, rear;
int t, n, k;
int main()
{
	//freopen("e://data.txt", "r", stdin);
	scanf("%d", &t);
	while(t --)
	{
		scanf("%d%d", &n, &k);
		sum[0] = 0;
		for(int i = 1; i <= n; ++ i)
		{
			scanf("%d", &A[i]);
			sum[i] = sum[i - 1] + A[i];
		}
		for(int i = n + 1; i <= n + k; ++ i)
			sum[i] = sum[i - 1] + A[i - n];
		front = rear = 0;
		int Max = sum[1];//初始化
		int l, r;
		l = r = 1;
		queue[front ++] = Queue(0, 0);//队列中存储最小元素和
		for(int i = 1; i < n + k; ++ i)
		{
			while(rear < front && queue[front - 1].v > sum[i])
				front --;
			queue[front ++] = Queue(i, sum[i]);
			while(rear < front && (i + 1 - queue[rear].pos) > k)//①这个需要在if之前进行判断
				rear ++;
			if(sum[i + 1] - queue[rear].v > Max)//[queue[rear].pos, i + 1]的最大值
			{
				Max = sum[i + 1] - queue[rear].v;
				l = queue[rear].pos + 1;
				r = i + 1;
			}
		}
		printf("%d %d %d\n", Max, (l - 1) % n + 1, (r - 1) % n + 1);
	}
	return 0;
}
*/

/*
第一次求解思路:
队列中存储长度在k之内的最大和,并存储l,r,在执行入队时候,需要遍历一次队列寻找出相连的元素,出队时判断l是否越界。
超时!

#include <iostream>
using namespace std;
const int INF = 0x7fffffff;
const int nMax = 100010;
int A[nMax];
struct Queue
{
	int l, r;
	int sum;
	Queue(){}
	Queue(int l, int r, int sum):l(l), r(r), sum(sum){}
}queue[nMax], ans;
int front, rear;
int t, n, k;
int main()
{
	//freopen("e://data.txt", "r", stdin);
	scanf("%d", &t);
	while(t --)
	{
		scanf("%d%d", &n, &k);
		int i;
		for(i = 0; i < n; ++ i)
			scanf("%d", &A[i]);
		front = rear = 0;
		int max;
		int l;
		for(i = 0; i < k; ++ i)
		{
			max = A[i];
			l = i;
			for(int j = rear; j < front; ++ j)
				if(queue[j].r == i - 1 && queue[j].sum + A[i] > max)
				{
					max = queue[j].sum + A[i];
					l = queue[j].l;
				}
			while(rear < front && queue[front - 1].sum < max)
				front --;
			queue[front ++] = Queue(l, i, max);
			ans = queue[rear];
		}
		for(int j = i; j < n + k; ++ j)
		{
			while(rear < front && queue[rear].l < j - k + 1) rear ++;
			i = j % n;
			max = A[i];
			l = i;
			for(int j = rear; j < front; ++ j)
				if(((i == 0 && queue[j].r == n - 1) || queue[j].r == i - 1) && queue[j].sum + A[i] > max)
				{
					max = queue[j].sum + A[i];
					l = queue[j].l;
				}
			while(rear < front && queue[front - 1].sum < max)
				front --;
			queue[front ++] = Queue(l, i, max);
			if(ans.sum < max)
				ans = queue[rear];
		}
		printf("%d %d %d\n", ans.sum, ans.l + 1, ans.r + 1);
	}
	return 0;
}
*/



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics