AcWing 1211. 蚂蚁感冒
原题链接
简单
作者:
Bear_King
,
2021-01-11 22:45:08
,
所有人可见
,
阅读 317
小球碰撞模型:蚂蚁感冒
本题所叙述的蚂蚁传染蚂蚁,归结于: 初始方向相向而行的小球之间碰撞,再反碰与初始方向同向而行的小球
本题重点:蚂蚁之间的相撞传染并换向而行,可以统一为:两只蚂蚁相撞传然后并穿越彼此继续按初始方向前进.只要能理解到这里,剩下的只剩分情况讨论了,因为题目数据范围较小所以不用考虑优化
最朴素的分情况讨论
#include<iostream>
#include<cmath>
using namespace std;
const int N = 50;
int n;
int q[N];
int main()
{
scanf("%d",&n);
/*
如果第一个感冒的蚂蚁是向右:左边向右+右边向左+1
如果第一个感冒的蚂蚁是向左:左边向右+右边向左+1
*/
for(int i = 0;i < n;i ++) scanf("%d",&q[i]);
int res = 0;
if(q[0] >= 0)
{
bool flag = false;
for(int i = 1;i < n;i ++)
{
//先找出所有对头走的蚂蚁,一定会被感染
if(q[i] < 0 && q[0] < abs(q[i]))
{
res ++;
flag = true;
}
}
if(flag)
for(int i = 1;i < n;i ++)
//有对头蚂蚁,则第一只感冒蚂蚁左边刚开始同向的蚂蚁就被感染
if(q[i] >= 0 && q[0] > abs(q[i]) )
res ++;
}
else
{
bool flag = false;
for(int i = 1;i < n;i ++)
{
//先找出所有对头走的蚂蚁,一定会被感染
if(q[i] >= 0 && abs(q[0]) > q[i])
{
res ++;
flag = true;
}
}
if(flag)
for(int i = 1;i < n;i ++)
//有对头蚂蚁,则第一只感冒蚂蚁左边刚开始同向的蚂蚁就被感染
if(q[i] < 0 && abs(q[0]) < abs(q[i]))
res ++;
}
cout<<res+1<<endl;
return 0;
}
要么,就根据第一只感冒的蚂蚁的位置来分割统计左右两边符合情况的数目
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55;
int n;
int x[N];
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> x[i];
int left = 0, right = 0; // 分别表示左边向右走的蚂蚁数量,和右边向左走的蚂蚁数量
for (int i = 1; i < n; i ++ )
if (abs(x[i]) < abs(x[0]) && x[i] > 0) left ++ ;
else if (abs(x[i]) > abs(x[0]) && x[i] < 0) right ++ ;
if (x[0] > 0 && right == 0 || x[0] < 0 && left == 0) cout << 1 << endl;
else cout << left + right + 1 << endl;
return 0;
}
说白了,就是脑筋急转弯,点个赞再走吧!