分析
根据题意只会给最近的位置传球,那么对位置排序只考虑前后位置计算出每个位置的传球方向,存在nx数组,1表示向右,0表示向左。
只有当nx数组中出现紧挨着的{… 1 0 …}时,表示有环。那么对于该环只需要计算出进入环的起点位置有几个,即为进入该环的所需传球数目。对每一个环都这样操作即可。由于每个位置的传球方向一定,所以一定不会出现一个点同时成为两个环的入口位置。
至于怎么判断进入环的起点位置个数很简单,只有2和1两种情况。如果是(紧挨着1 0环左边至少有一个连续1)1 1 0 0(紧挨着1 0环右边至少有一个连续0)就是2个起点,否则就是1起点。在纸上画一画就知道了。
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int nums[N], nx[N];
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> nums[i];
}
sort(nums, nums + n);
nx[0] = 1;
for(int i = 0; i < n - 1; i++) {
int a = nums[i] - nums[i - 1], b = nums[i + 1] - nums[i];
if(a > b) {
nx[i] = 1;
}
}
int ans = 0;
for(int i = 1; i < n; i++) {
if(nx[i] == 0 && nx[i - 1] == 1) {
if(i - 2 >= 0 && nx[i - 2] == nx[i - 1] && i + 1 < n && nx[i + 1] == nx[i]) ans += 2;
else ans++;
}
}
cout << ans << endl;
return 0;
}
大佬nums[i-1]好像越界了!
大佬,怎么想出来的,太强了,棒棒
写代码一定注意不要越界!