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

Chenxuhang_play · 2025-07-24 21:49:02 · 题解

通过首尾相减再加上 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。

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

代码如下。

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