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

抢一波题解。

Solution

首先求期望拿到的核桃卷段数量，由于是期望，所以不存在什么核桃卷在这之前已经被拿走的情况，所以拿走的段数就是 $K-P+1$。

//求期望拿到的 
for(int i=1;i<=n;i++)
    if(r[ans]-l[ans]+1<r[i]-l[i]+1)
        ans=i;
cout<<ans<<"\n";

然后求实际拿到的，我们开一个标记数组 $vis$，表示这个点到底有没有被拿走，没被拿走就拿走并标记。

for(int i=1;i<=n;i++){
    for(int j=l[i];j<=r[i];j++){
        if(!vis[j])vis[j]=1,cnt[i]++;//没人拿，拿走，计数器加一
        else ;//被人拿了 
      }
		if(cnt[ans]<cnt[i])ans=i;
}

整体代码。

#include<bits/stdc++.h>
using namespace std;
int m,n,l[1145],r[1145],ans,cnt[1145];
bool vis[1145];
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>m>>n;
	for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
	//求期望拿到的 
	for(int i=1;i<=n;i++)if(r[ans]-l[ans]+1<r[i]-l[i]+1)ans=i;
	cout<<ans<<"\n";
	ans=0;
	for(int i=1;i<=n;i++){
		for(int j=l[i];j<=r[i];j++){
			if(!vis[j])vis[j]=1,cnt[i]++;//没人拿，拿走，计数器加一
			else ;//被人拿了 
		}
		if(cnt[ans]<cnt[i])ans=i;
	}
	cout<<ans;
	return 0;
}