AcWing 1211. 蚂蚁感冒
原题链接
简单
作者:
wjie
,
2020-07-28 11:44:35
,
所有人可见
,
阅读 501
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 55;
struct Ant{
int pos;
bool isCold;
bool operator < (const Ant& a) const {
return abs(pos) < abs(a.pos);
}
}ants[N];
int main()
{
int n;
scanf("%d", &n);
ants[0].isCold = true;
for (int i = 0; i < n; ++i) scanf("%d", &ants[i].pos);
sort(ants, ants+n);
int l = 0, r = n-1, res = 0;
while (l <= r)
{
while (l <= r && ants[l].pos < 0)
{
if (ants[l].isCold) res++;
l++;
}
while (l <= r && ants[r].pos > 0)
{
if(ants[r].isCold) res++;
r--;
}
for (int i = l; i < r; ++i)
{
if (ants[i].pos * ants[i+1].pos < 0)
{
ants[i].isCold = ants[i+1].isCold = ants[i].isCold | ants[i+1].isCold;
ants[i].pos *= -1;
ants[i+1].pos *= -1;
}
}
}
printf("%d", res);
return 0;
}