题目简述
Sereja 是一名程序员,他喜欢参加 Codesorfes 比赛。不过,乌兹兰的网络连接不太好,所以 Sereja 有时会跳过比赛。
Codesorfes 有两种类型的比赛,分为 Div1 和 Div2。 Div1 和 Div2 这两轮可以同时进行(Div1 轮不能在没有 Div2 的情况下进行)。每一轮都有一个唯一的标识符,各轮按开始时间顺序编号。同时运行的各轮标识符相差一个,而且 Div1 轮的标识符总是较大。
Sereja 是一名初学者,因此他只能参加 Div2 类型的比赛。此刻他正在参与 Div2 回合,其标识符为 $x$。Sereja 清楚地记得,在这一轮之前,他正好下过 $k$ 轮。此外,他还记得他参加过的各轮比赛的所有标识符,以及与它们同时进行的各轮比赛的所有标识符。Sereja 不记得他错过的任何一轮比赛。
Sereja 想知道他错过的 Div2 轮最少和最多会是多少?帮他找出这两个数字。
题目分析
可以先将这 $k+1$ 轮比赛排序,算出每两轮之间错过的场数,设为 $a$,如果要是最多,那么这 $a$ 轮都是 div2。要是最少的话,就要让 div1 和 div2 同时进行的场数尽可能多,即最多有 $\lfloor \frac{a}{2} \rfloor$ 轮,有可能 $a$ 是奇数,那么还要多一轮 div2,所以最少的场数就是 $\lfloor \frac{a}{2} \rfloor+a \bmod 2$,累加即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define random(a,b) (rand()%(b-a+1)+a)
#define se second
#define fi first
#define pr pair<int,int>
#define pb push_back
#define ph push
#define ft front
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,a,b) for(int i=a;i>=b;i--)
#define mem(a,b) memset(a,b,sizeof a)
const int N=4100;
int x,k,opt,ans1,ans2;
pr a[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>x>>k;
For(i,1,k)
{
cin>>opt;
if(opt==2)
{
cin>>a[i].fi;
a[i].se=a[i].fi;
}
else
{
cin>>a[i].fi>>a[i].se;
}
}
a[k+1].fi=x;
sort(a+1,a+1+k);
For(i,1,k+1)
{
int temp=a[i].fi-a[i-1].se-1;
ans1+=temp/2+(temp%2);
ans2+=temp;
}
cout<<ans1<<" "<<ans2;
return 0;
}
标签:题解,Sereja,cin,401B,fi,标识符,Div2,define
From: https://www.cnblogs.com/zhuluoan/p/18199682