\(\mathfrak{1st.\ Preamble\ |}\) 前言
题目传送门:CF1942C1 Bessie's Birthday Cake (Easy Version) 。
蒟蒻在洛谷上第一篇通过的题解。
\(\mathfrak{2nd.\ Reasoning\ |}\) 思路
其实只需要把选中的点组成一个新的多边形,然后我们就可以发现有 \(x\) 个点的多边形可以连出 \(x-2\) 个三角形。此外,两个位置差为 \(2\) 的点也是可以连出一个三角形。
于是我们只需要对点的位置排个序,然后从头到尾遍历一遍,发现差为 \(2\) 的相邻两点就 cnt++
,最后输出 \(x-2+cnt\) 就是最终答案了。
注意:首尾点的位置差为 \(n-a_x+a_1\),如果这个为 \(2\) 也得 cnt++
。
时间复杂度:每组数据 \(O(n \log_2 n)\)。
\(\mathfrak{3rd.\ Code\ |}\) 代码
#include <iostream>
#include <algorithm>
#include <string.h>
#define ll long long
using namespace std;
const int N=2e5+10;
int T,n,x,y,ans,a[N];
int main(){
//数据较大,关闭同步流加快输入输出速度
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>T;
while(T--){
ans=0,memset(a,0,sizeof(a)); //保险起见清空一下
cin>>n>>x>>y;
for(int i=1;i<=x;i++)cin>>a[i];
sort(a+1,a+x+1); //排序点的位置
for(int i=2;i<=x;i++)if(a[i]-a[i-1]==2)ans++;
if(n-a[x]+a[1]==2)ans++; //判断首尾点的位置差
cout<<ans+x-2<<endl;
}
return 0;
}
标签:int,题解,差为,Version,Easy,Birthday,include
From: https://www.cnblogs.com/Simon-Wu/p/18358827