专栏文章

题解：P1311 [NOIP2011 提高组] 选择客栈

bbravo11111111
P1311题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqixlfp
此快照首次捕获于
2025/12/04 05:33
3 个月前
此快照最后确认于
2025/12/04 05:33
3 个月前
查看原文

解题想法

这道题我们如果枚举每两个客栈，时间肯定是要超的。但这到题要求选两个颜色相同的客栈，我们可以枚举每种颜色的客栈,时间复杂度为 O(k×n)O(k\times n)。

解题思路

我们不难可以发现，当两个颜色相同客栈中间，有满足最小花费小于 pp 的客栈时，那么两个客栈中后面的那个客栈一定能和前面的那个客栈及其他前面所有与他颜色相同客栈配对。了解这点，就可以做出这道题。

AC代码

CPP
#include<bits/stdc++.h>
using namespace std;
long  long n, k,p,a[200005],ans,b[200005],sum,num,ma,x,nu;
int main(){
	scanf("%d%d%d",&n,&k,&p);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
	for(int i=0;i<k;i++){//枚举颜色
	long long t=0,answer=0,mi=1e18;
		for(int j=1;j<=n;j++)
		{
			mi=min(mi,b[j]);
			if(a[j]==i){//颜色相同
				t++;
				if(t>1)
					if(mi<=p)
						answer=t-1;//更新最前面可以与它配对的客栈
					mi=b[j];
					ans+=answer;//相加
				}
			}
		}
	printf("%d",ans);
	return 0;
	}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...