欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[思维]蚂蚁感冒

程序员文章站 2024-03-18 22:37:58
...

[思维]蚂蚁感冒

蚂蚁的问题都有相似性

从相遇等同于擦肩而过开始推导

如果第一只蚂蚁是正值

那么他后面所有负值蚂蚁都会和他碰面

(如果有的话) 那么这些蚂蚁肯定会和他背后所有和正值的蚂蚁碰面

同理 负值也如此

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int arr[MAXN] = {0};

bool cmp(int a, int b)
{
	return abs(a) < abs(b);
}

int main()
{	
	int n;
	
	cin>>n;
	
	for(int i = 0; i < n; i++)
		cin>>arr[i];
		
	int rval = arr[0];
	
	sort(arr, arr + n, cmp);
	
	int rpos = 0;
	
	while(arr[rpos] != rval)
		++rpos;
		
	int ans = 1;
	
	int ra = 0, rb = 0;
	
	for(int i = rpos - 1; i >= 0; i--)
	{
		if(arr[i] > 0)
			ra++;
	}
	
	for(int i = rpos + 1; i < n; i++)
	{
		if(arr[i] < 0)
			rb++;
	}
	if(ra > 0 && rb > 0)
		ans = (ra + rb + 1);
		
	else if(ra == 0)
		ans = (rb + 1);
		
	else if(rb == 0)
		ans = ra + 1;

	cout<<ans<<'\n';
	return 0;
}