首页 > 其他分享 >happiness(栈)

happiness(栈)

时间:2024-09-19 16:06:20浏览次数:7  
标签:int max top MAX stack happiness

happiness(栈)


// happiness
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100000

// 函数声明
int max_happiness(int n, int w[]);

int main()
{
	int n;

	// 输入物品数量
	scanf("%d", &n);

	// 输入每个物品的满意度
	int w[MAX_N];
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &w[i]);
	}

	// 输出最大happiness
	printf("%d\n", max_happiness(n, w));

	return 0;
}

int max_happiness(int n, int w[])
{
	int prefix_sum[MAX_N + 1]; // 前缀和数组
	int left[MAX_N];		   // 每个物品的左边界
	int right[MAX_N];		   // 每个物品的右边界
	int stack[MAX_N];		   // 单调栈
	int top;				   // 栈顶指针
	int max_happiness = 0;	   // 记录最大happiness

	// Step 1: 计算前缀和
	prefix_sum[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		prefix_sum[i] = prefix_sum[i - 1] + w[i - 1];
	}

	// Step 2: 使用单调栈计算每个物品的左边界
	top = -1; // 初始化栈为空
	for (int i = 0; i < n; i++)
	{
		while (top != -1 && w[stack[top]] >= w[i])
		{
			top--;
		}
		if (top == -1)
		{
			left[i] = -1; // 没有比当前元素更小的,左边界为-1
		}
		else
		{
			left[i] = stack[top]; // 栈顶元素即为左边第一个比当前元素小的
		}
		stack[++top] = i; // 当前元素入栈
	}

	// Step 3: 使用单调栈计算每个物品的右边界
	top = -1; // 清空栈
	for (int i = n - 1; i >= 0; i--)
	{
		while (top != -1 && w[stack[top]] >= w[i])
		{
			top--;
		}
		if (top == -1)
		{
			right[i] = n; // 没有比当前元素更小的,右边界为n
		}
		else
		{
			right[i] = stack[top]; // 栈顶元素即为右边第一个比当前元素小的
		}
		stack[++top] = i; // 当前元素入栈
	}

	// Step 4: 计算最大happiness
	for (int i = 0; i < n; i++)
	{
		int l = left[i] + 1;						   // 左边界+1
		int r = right[i];							   // 右边界
		int total_sum = prefix_sum[r] - prefix_sum[l]; // 通过前缀和计算区间的总和
		int current_happiness = total_sum * w[i];	   // happiness计算公式
		if (current_happiness > max_happiness)
		{
			max_happiness = current_happiness; // 更新最大happiness
		}
	}

	return max_happiness;
}

标签:int,max,top,MAX,stack,happiness
From: https://www.cnblogs.com/yesno233233/p/18420751

相关文章

  • 2024-09-04:用go语言,给定一个长度为n的数组 happiness,表示每个孩子的幸福值,以及一个正
    2024-09-04:用go语言,给定一个长度为n的数组happiness,表示每个孩子的幸福值,以及一个正整数k,我们需要从这n个孩子中选出k个孩子。在筛选过程中,每轮选择一个孩子时,所有尚未选中的孩子的幸福值都会减少1。需要注意的是,幸福值不能降低到负数,只有在其为正数时才能减少。我们的目标是尽可......
  • 2024-09-04:用go语言,给定一个长度为n的数组 happiness,表示每个孩子的幸福值,以及一个正
    2024-09-04:用go语言,给定一个长度为n的数组happiness,表示每个孩子的幸福值,以及一个正整数k,我们需要从这n个孩子中选出k个孩子。在筛选过程中,每轮选择一个孩子时,所有尚未选中的孩子的幸福值都会减少1。需要注意的是,幸福值不能降低到负数,只有在其为正数时才能减少。我们的目标是......
  • Codeforces Round 946 (Div. 3) G Money Buys Less Happiness Now(反悔贪心)
    MoneyBuysLessHappinessNow1.题目大意:有n天,每天可以赚x块钱,然后每天可以通过花\(C_{i}\)块钱购买1点快乐值,然后每天赚的钱至少要在下一天才能用,问最多能获得多少快乐值。2.解题思路:我们发现天数变得很多,不能像e题那样dp了,所以要用贪心。具体来讲,我们碰到当前能买的就直接......
  • E. Money Buys Happiness
    原题链接题解观察到h不大于1e5,于是拿h做文章如果想要在第\(i\)个月的幸福值达到\(j\)那么第\(i-1\)个月的幸福值一定能达到\(j-h_i\)而且\(cost_{[i-1][j-h_i]}+c_i\leqx·(i-1)\)记得用滚动数组优化,因为这里\(i\)只和\(i-1\)的小幸福值有关code#include<bit......
  • G. Money Buys Less Happiness Now
    原题链接题解假如最后有\(k\)个月购买过幸福,那么这\(k\)个月的价格一定是前\(k\)小的code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);intt;cin>>t;whil......
  • Codeforces 1974G Money Buys Less Happiness Now
    考虑到有一种贪心的思路就是能选就选。显然这是错的,因为可能存在后面更优的情况,即当\(c_i>c_j(i<j)\)时,选\(j\)肯定比选\(i\)更优,因为后面剩下的更多且中间也留下了一些。于是考虑反悔贪心。还是一样的,如果能选就一定选上。否则来说,考虑对于当前已经选了的中的最大......
  • [国家集训队] happiness 题解
    发现可以做如下建图:对于前两组输入,从\(s\)向所有代表学生的点连一条边,容量为其学习文科的喜悦值;从所有代表学生的点向\(t\)连一条边,容量为其学习理科的最大值。对于后四组输入,建两个点\(x,y\),从\(s\)向\(x\),从\(y\)向\(t\)分别连容量为相邻两人同时学文/理时额......
  • 初中英语优秀范文100篇-044Can Money Buy Happiness?钱能买到幸福?
    PDF格式公众号回复关键字:SHCZFW044记忆树1Canmoneybuyhappiness?翻译钱能买到幸福吗简化记忆幸福句子结构主语:money(金钱)谓语:canbuy(能够购买)宾语:happiness(幸福)这是一个陈述句,谓语动词"canbuy"表达了金钱的购买能力。宾语"happiness"指的是幸福。整个句子在语......
  • 【BZOJ2127】happiness(网络流)
    建模:首先\(S\)向每一个\((i,j)\)连一条它选文科的价值的边,每一个\((i,j)\)向\(T\)连一条它选理科的价值的边。然后对于两个点\(a,b\),假设他们同时选理科能获得......
  • [国家集训队]happiness
    洛谷题面这是一道关于网络流的建模题目首先如果用最大流考虑,发现很难建出这个图,所以放弃然后考虑用最小割考虑我们发现题目中要我们求出最小价值,那么按照最大价值=......