[NOIP2011]选择客栈

发布于 2017-08-18  24 次阅读



题目(vijos)
这道题我和那个辣鸡算法不同。
首先,对于每个颜色,开一个d[i]数组用来存有多少个客栈是第i种颜色,
然后,对于第i种颜色,循环一遍n个客栈,找到第一个颜色与i相同的客栈,分两种情况:
一.当前客栈的最低消费<=p;
二.当前客栈的最低消费>p;
对于每一种情况又分两种情况:
1.当前客栈之前没有颜色与i相同的客栈;
2.当前客栈之前有颜色与i相同的客栈;
设cnt1为跑到第一个最低消费<=p(不论颜色)时颜色与i相同的客栈共有多少个,cnt2为剩下未考虑的颜色与i相同的客栈有多少个。
设答案为cnt。
利用乘法原理,明显地,当情况为一.1时,cnt=cnt+1*(cnt2-cnt1);
当情况为一.2时,cnt=cnt+(cnt1-1)*(cnt2-cnt1+1)。
然后接着跑。
当情况为二.1时,cnt1++;
当情况为二.2时,cnt=cnt+cnt1*(cnt2-cnt1);
处理一下细节即可.。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
int n,k,p;
struct node{
	int col;
	int val;
}e[200005];
int cnt=0;
int d[55];
int main()
{
	scanf(
	for (int i=1;i<=n;++i)
	{
		scanf(
		d[e[i].col]++;
	}
	for (int i=0;i<k;++i)
	{
		bool flag=false;
		bool flag2=false;
		bool flag3=false;
		int cnt1=0,cnt2=d[i];
		for (int j=1;j<=n;++j)
		{
			if (e[j].col!=i && flag2 && e[j].val<=p)
			{
				flag=true;
			}
			else if (e[j].col==i)
			{
				flag2=true;
				cnt1++;
				if (e[j].val<=p) flag3=true;
			}
			if (flag3)
			{
				cnt=cnt+(cnt1-1)*(cnt2-cnt1+1);
				cnt=cnt+1*(cnt2-cnt1);
				flag=flag2=false;
				flag3=false;
				cnt2=cnt2-cnt1;
				cnt1=0;
			}
			else if (flag)
			{
				cnt=cnt+cnt1*(cnt2-cnt1);
				flag=flag2=false;
				flag3=false;
				cnt2=cnt2-cnt1;
				cnt1=0;
			}
		}
	}
	printf(
	return 0;
}