Java教程

算法题-焦虑的蚂蚁

本文主要是介绍算法题-焦虑的蚂蚁,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述

    一条长度为n的小径上,挤满了m只蚂蚁,每只蚂蚁有一个初始前进方向(向左或是向右),蚂蚁们的前进速度相同且均为1。小径的两端,均放着上了锁的箱子,箱内盛有美味的食物,蚂蚁们争相前进离开小径。不幸的是,小径十分狭窄,当两只蚂蚁相遇时,它们不得不掉头向着相反的方向前进。当所有的蚂蚁都离开小径时,锁才能够打开,蚂蚁们才能获得美味的食物。因此,蚂蚁们十分焦虑,它们想知道,到底花费多少的时间,它们才能够吃到美味的食物。你能够帮助他们解决问题吗?

输入描述:

第一行,2个整数n,m(1≤m<n≤100000,n,m均为整数),分别代表小径的长度,蚂蚁的数量。

接下来m行,每行2个数,分别代表蚂蚁的初始方向(0代表向左,1代表向右),蚂蚁的初始坐标x满足x为整数且0<x<n,蚂蚁走到坐标0或坐标n即代表离开小径。

数据保证每个坐标上最多有1只蚂蚁。数据保证给出的蚂蚁初始坐标为从小到大。

输出描述:

一行,对结果四舍五入,输出1个整数,代表蚂蚁吃到美味的食物的时间。

示例1
输入
复制

50 10
1 6
0 15
0 19
1 20
0 22
0 25
1 36
0 39
1 40
1 42

输出
复制

44

这题很有趣,所以在写完后还是想写一片题解,防止以后忘记,这题并非模拟全部过程,那样根本不可能写出来,或者说我写不出来,两只蚂蚁碰面交换方向,因为不用去区分蚂蚁,所以可以认为所有的蚂蚁都是相同的,这样就可以看作两个蚂蚁相遇见时会互换位置,或者可以理解为穿过对方,这样就可以写出来了,只要找到一只蚂蚁理终点线最远(注意有方向),他的距离就是答案;

#include <bits/stdc++.h>
using namespace std;
long long power(int k, int a);
bool isPrime(long long n);
int main()
{
    long long a=0,b=0,d=0, i=0, T, s=0, le;
    long long a1=0, a5=0, a10=0,n,m,res=0,arr2[100000];
    char sr[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J','K','L'};
    int N,R,sym=1, arr[100000];
    float gpa, s_gpa=0;
    char c;
    string str;

    cin>>n>>m;
//     a=100000;
//     b=-100000;
    for (i=0;i<m;i++){
//         printf("%d/%d\n",a,b);
        cin>>d>>s;
        if (d==1) s = (n-s); 
        res = max(res,s);
    }

    
    cout<<res<<endl;
    
//     printf("%lld %lld %lld %lld",max-max2,max-min2,max2-min2,max2-min);
    
//         cout<<b-a<<endl;
//     printf("%.2f %d %d",double(s)/n,b,a);

//     if (sym > 0)
//         str = "Nancy";
//     else
//         str = "Johnson";
//     cout<<str<<endl;

    

    
//     cin>>T;
//     for (int i=0; i<T; i++) {
//         cin>>n;
//         if (n==1) {
//             printf("No\n");
//             continue;
//         }
//         b=0;
//         for(int j=2;j<n-1;j++){
//             if (n % j == 0) {
                
//                 b=1;
//                 break;
//             }
//         }
//         if (b==1) {
//             printf("No\n");
//         } else {
//             cout<<"Yes"<<endl;
//         }
        
        
        
        
//     }
        
//         printf("%.1f", res);
    

            
            
        
   
    // cout<<"positive:"<<endl;
    // cout<<"negative:"<<b<<endl;
}

long long power(int k, int a) {
    if (a == 0) return 1;
    long long res = 1;
    for (int i=0; i<a; i++) {
        res *= k;
    }
    return res;
}

bool isPrime(long long n) {
    for(int j=2;j<n-1;j++){
        if (n % j == 0) {
            return false;
        }
    }
    return true;
}
这篇关于算法题-焦虑的蚂蚁的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!