题目传送门

1、题目大意

这题讲了一个烹饪节目，大厨烘培了一条长达

L

米的核桃卷，并奖励给

N

名观众。核桃卷分成 L 个小段，分别是

1

到

L

。每个观众写下

P

和

K

。但因为有先后顺序，所以有一些观众会有一些部分拿不到。题目要我们求出哪位观众期望获得最多的核桃卷段，以及哪位观众实际获得的核桃卷段最多。

2、思路

1、期望值

期望值我们可以用

k_i-p_i

和当前最大值作比较，因为如果有相同的取序号较小，所以我们要有大于当前最大值的才更新。

2、实际值

因为

L

（

1 \leq L \leq 1000

）并且

N

（

1 \leq N \leq 1000

），

L

和

N

的值比较小，所以我们可以直接暴力来搜索一遍，用一个数组来标记是否有人拿过。和上面同理，因为如果有相同的取序号较小，所以我们要有大于当前最大值的才更新。

3、代码

CPP

#include<bits/stdc++.h>
using namespace std;
int L,n,p[1005],k[1005],f[1005],zd=-1,wz; //记得求最大值初始为-1，防止p[i]=k[i] 
signed main(){
	cin>>L>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>p[i]>>k[i];
		if(k[i]-p[i]>zd) zd=k[i]-p[i],wz=i;//处理期望值 
	}
	printf("%d\n",wz);
	zd=-1;
	for(int i=1;i<=n;i++){
		int sum=0;
		for(int j=p[i];j<=k[i];j++)
		if(!f[j]) sum++,f[j]=1;//判断是否被拿过 
		if(sum>zd) zd=sum,wz=i;//处理实际值 
	}
	printf("%d",wz);
}

最后再提醒一句：题解仅供学习参考使用，请勿抄题解。

写作不易，求点赞。

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

文章操作