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

· · 题解

题目传送门

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、代码

#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);
}

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

写作不易，求点赞。