# A case of 2.11 falling ant in bokeoj (simulation) & poj1852 ants (greedy) (ant problem)

Both questions are about ant climbing.. So it's put together.

The first one is the complex test, because different ants collide to exchange speed, so in different cases, one move is equivalent to relay, and two opposites are equivalent to transposition. So for an ant with a speed of 0, if there is an ant walking towards itself on both sides, the direction remains the same, but the initial position becomes the initial position of the ant at the last exchange position.

If you think about it carefully, you can first calculate how many ants are on the left and right sides, and treat the ants you can meet as if they are all dead together. The time when the immobile ants fall is the time when the first living ant falls, and the direction where the immobile ants fall is the direction where the number of the left and right sides is more. Finally, the simulation is enough.

```#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <cmath>
#include <climits>

using namespace std;

const int INF = INT_MAX;

int FindCommon(int x, int y){
int minabs = min(abs(x), abs(y));//Find the absolute value of the common part
if(x+y > 0) return minabs+1;
else if(x+y < 0) return -(minabs+1);
else return 0;
}

int main(){
//	freopen("in.txt", "r", stdin);
int N, pos, way, current, change, number, number1, number2;
int stick;
while(~scanf("%d", &N)){
memset(stick, 0, sizeof(stick));
number = number1 = number2 = 0;
for(int i = 0; i < N; i++){
scanf("%d %d", &pos, &way);
stick[pos] = way;
if(way == 0) current = pos;
}
change = current;
while(change--){
if(stick[change] == 1) number1++;
if(change == 0) break;
}
change = current;
while(change++){
if(stick[change] == -1) number2--;
if(change == 100) break;
}
number = FindCommon(number1, number2);
int ans, flag = false;
if(number > 0){//Forward residue
change = current;
while(number > 0){
change--;
if(stick[change] == 1) number--;
}
ans = 100 - change;
}
else if(number < 0){//Negative surplus
change = current;
while(number < 0){
change++;
if(stick[change] == -1) number++;
}
ans = change;
}
else flag = true;
if(flag) printf("Cannot fall!\n");
else printf("%d\n", ans);
}
return 0;
}```

Link to previous question: click here

When ants meet at the same speed, they will turn back, which can be regarded as the two sides do not affect each other.

This problem can be simulated at the beginning. First, arrange the ants in order and then find the ants in the middle and left and right of the pole. The minimum value is the maximum value of the ants closest to the pole going outward, and the maximum value is the maximum value of the ants farthest from the pole going inward. But there is a disadvantage of this method, that is, the boundary situation is not easy to discuss. It's all in the middle of the bar on the left or right. If there's one in the middle of the bar, we'll discuss the scoring situation. If there's more than one in the middle of the bar, we'll discuss... Too much trouble to give up..

The best way to solve this problem is to be greedy. In fact, we should think of greedy at the beginning.. Traverse all ants to find the most value in two directions.

For this problem, the amount of data is 1000000. Pay attention to defining it as a global variable.

```#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <cmath>
#include <climits>

using namespace std;

const int MAXN = 1000005;
const int INF = INT_MAX;

int stick[MAXN];

int main(){
//	freopen("in.txt", "r", stdin);
int M, L, n;
scanf("%d", &M);
while(M--){
scanf("%d %d", &L, &n);
for(int i = 0; i < n; i++){
scanf("%d", &stick[i]);
}
int maxtime = 0, mintime = 0;
for(int i = 0; i < n; i++){
maxtime = max(maxtime, max(stick[i], L-stick[i]));
mintime = max(mintime, min(stick[i], L-stick[i]));
}
printf("%d %d\n", mintime, maxtime);
}
return 0;
}```  377 original articles published, 64 praised, 150000 visitors+

Added by MrCool on Tue, 18 Feb 2020 12:34:50 +0200