题解：P13413 [COCI 2012/2013 #4] OREHNJACA

通过首尾相减再加上

1

，可以得到每个选手期望获得的核桃卷段的长度。使用打擂台可以得到期望获得的核桃卷段的长度最长的观众。

实际获得的核桃卷段的长度可以考虑如下方案实现：

建立一个长度为 $L$ 的数组 $a$ ，对于 $i\in[1,L]$ ， $a_i$ 表示核桃卷段是否已经被拿走。 $a_i=1$ 表示核桃卷段没有被取走， $a_i=0$ 表示该段已经被拿走。
对于每次输入的 $l,r$ ，使用变量 $sum$ 记录对于 $i\in[l,r]$ 中的 $a_i$ 的和。每次取走之后将 $a_i$ 设为 $0$ 。

用这种方法可以求出每个观众实际获得的核桃卷段的长度。

代码如下。

CPP

#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long L,n;
	cin>>L>>n;
	int a[L+5],l,r,maxn=0,mn=0,maxa=0,ma=0,sum=0;
	for(long long i=1;i<=L;i++) a[i]=1;
	for(long long i=1;i<=n;i++)
	{
		cin>>l>>r;
		if(maxn<r-l+1)
		{
			maxn=r-l+1;
			mn=i;
		}
		sum=0;
		for(long long j=l;j<=r;j++)
		{
			sum+=a[j];
			a[j]=0;
		}
		if(maxa<sum)
		{
			maxa=sum;
			ma=i;
		}
	}
	cout<<mn<<endl<<ma;
	return 0;
}

题解：P13413 [COCI 2012/2013 #4] OREHNJACA

文章操作

相关推荐

评论

题解：P13413 [COCI 2012/2013 #4] OREHNJACA