暴力十分好想但你写不出来qwq
正解十分好写但你想不出来qaq
我们先读题，发现k其实没什么用
同时暴力枚举两个客栈的话会超时，所以只能同时枚举一个。我们枚举第二个客栈，然后用第二个客栈反推出前面的方案数。
思路就是，从1到n枚举，输入颜色color和价钱price，我们需要记录一个距离第二个客栈最近且价钱合理(小于等于p)的咖啡厅的客栈位置，用变量now记录。
然后开三个辅助数组，last[i]表示最后一个以i为颜色的客栈的位置，cnt[i]表示以i为颜色的客栈总数，sum[i]可以看作是一个临时数组，用来存储当前的方案数。
可以这么想，当前枚举到一个客栈i，这个i是第二个客栈，那么显然第一个客栈一定在第二个客栈之前，编号必定是0~i-1之间的一个数。如果我发现枚举的时候在某一个客栈前面有一个价钱合理的咖啡厅，那么在这之前的任何一个同色客栈都是第一个客栈可以选的，那么统计一下数量，这就是当前的方案数。
然后更新last数组，更新ans，让cnt[color]++，这样从左到右地推过来就好了。
这个解法简化于暴力算法，暴力算法要循环三层，一层1客栈，二层2客栈，3层合理的位置，这样做显然不行，而我们做的就是去优化掉两层，从枚举2客栈出发推出1客栈的位置和所有可行方案，所以这样做是正确的。最后输出即可。
我要评论 1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
5 using namespace std;
6
7 int n,k,p;
8 int color,price,now,ans;
9 int last[55],sum[55],cnt[55];
10
11 int main()
12 {
13 ios::sync_with_stdio(false);//关同步,让你的cin,cout快过scanf,printf!
14 cin>>n>>k>>p;
15 for(int i=1; i <= n; i++){
16 cin>>color>>price;
17 if(price <= p)
18 now=i;
19 if(now >= last[color])
20 sum[color]=cnt[color];
21 last[color]=i;
22 cnt[color]++;
23 ans += sum[color];
24 }
25 cout<<ans<<"\n";//\n比endl快8倍
26 return 0;
27 }
如对本文有疑问， 点击进行留言回复！！
SP8093 JZPGYZ - Sevenk Love Oimaster(广义SAM)
[2020牛客暑期多校训练营第三场] L.Problem L is the Only Lovely Problem 字符串函数
Qt——BUG：构造函数中new了控件并隐藏了，后续显示时位置不对？
PAT甲级 1087. All Roads Lead to Rome (30) （dijkstra）
网友评论