题目传送门: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; }
Comments NOTHING