ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 简单
  4. 正文

[洛谷P2088] 果汁店的难题(贪心 + 模拟)

2022年3月25日 510点热度 0人点赞 0条评论

题目传送门:P2088 果汁店的难题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这是今天的一道练习题,我一看普及+/提高感觉蛮难的,其实想一下也还好。主要是数据非常小,复杂度是O(N ^ 2)。

题目大意请看原题。

思路

我们用used来表示某种水果被用在一个榨汁机里,具体在哪个榨汁机不重要。

cnt表示当前有多少个榨汁机里面是有东西的。

先将整个序列离线,然后遍历。如果水果x已经used了,说明当前有一个榨汁机正在榨水果x,直接continue。

如果cnt < K就直接把水果x放到一个干净的榨汁机里,如果cnt == K(已经满了),就要决策将哪种水果对应的榨汁机清洗,有两种情况:

  • 这水果x后面不会再用到水果y,那么就把水果y的榨汁机清洗。
  • 如果水果x后面的水果都会被用到,那么就把“x之后第一次用到且已经在使用的的水果当中的最后一个”清洗。

如下图:

我们可以将“找要清洗的榨汁机种类”写一个函数,方便理解。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 109;
int a[maxn];
bitset<maxn> used;//表示某种水果是否正在榨汁机中 
int cnt = 0;//表示已经使用的榨汁机数量 
int K, N;
int theLast(int st)
{
	int res = 0;
	bitset<maxn> vis;
	
	for(int i = st;i <= N; ++ i)
		if(!vis[a[i]] && used[a[i]])res = a[i], vis[a[i]] = 1;
	for(int i = 1 ;i < st; ++ i)if(!vis[a[i]] && used[a[i]])return a[i];
	return res;
}

signed main()
{
	cin >> K >> N;
	for(int i = 1;i <= N; ++ i)cin >> a[i];	
	
	int ans = 0;
	for(int i = 1;i <= N; ++ i)
	{
		int x = a[i];
		if(used[x])continue;
		
		if(cnt < K)used[x] = 1, cnt ++;
		else
		{
			int y = theLast(i);
		//	printf("y = %lld\n", y);
			used[y] = 0;
			used[x] = 1;
			ans ++;
		}
	}
	printf("%lld\n",ans);
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ 思维 模拟 洛谷 算法竞赛 贪心
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号