例56 螞蟻
問題描述
n只螞蟻以每秒1cm的速度在長為Lcm的竿子上爬行，當螞蟻爬到竿子的端點時就會掉落，由于竿子太細，兩只螞蟻相遇時，它們不能交錯通過，只能各自反向爬回去，螞蟻反向不需耗時，對于每只螞蟻，我們知道它距離竿子左端的距離xi，但不知道它當前的朝向，請計算各種情況當中，所有螞蟻落下竿子所需的最短時間和最長時間，
例如：竿子長10cm，3只螞蟻位置為2 6 7，最短需要4秒(左、右、右)，最長需要8秒（右、右、右），
輸入
第1行：2個整數N和L，N為螞蟻的數量，L為桿子的長度(1 <= L <= 10^9, 1 <= N <= 50000)
第2 ~ N + 1行：每行一個整數A[i]，表示螞蟻的位置(0 < A[i] < L)
輸出
輸出2個數，中間用空格分隔，分別表示最短時間和最長時間，
輸入樣例
3 10
2
6
7
輸出樣例
4 8
（1）編程思路，
最短時間較容易求，如果每只螞蟻一開始就向著距離自己最近的竿子那一端爬，即在坐標0~L/2之間的螞蟻朝著左端爬，L/2~L之間的螞蟻朝著右端爬，那么螞蟻之間就不會相遇（因為螞蟻的速度是一樣的），這樣每只螞蟻的爬行時間對于自己來說都是最小的，又因為是直接朝著自己的方向走的，沒有回傳也沒有相遇，所以在所有螞蟻都處于自己最短的時間中求出用時最長的那一個時間，就是所有螞蟻的最短用時，
要使時間最長，螞蟻一定會相遇，因為只有不斷相遇，不斷折返，才能增加螞蟻的爬行時間，在實際計算時，無需根據每只螞蟻的折返情況來計算時間，
因為可以將所有螞蟻都視作相同無差別的，那么上圖中，若螞蟻1與螞蟻2相遇了，我們可以將螞蟻1變身成螞蟻2，螞蟻2變身成螞蟻1，這樣的話，就可以看做螞蟻其實并沒有回傳，而是“擦身而過”，這樣每只螞蟻每次遇到別的螞蟻后就不斷變身，那么就相當于每只螞蟻是獨立運動的，并不會影響其運動方向與軌跡，這樣，在所有螞蟻都處于自己最長的時間中求出用時最長的那一個時間，就是所有螞蟻的最長用時，
（2）源程式，
#include <stdio.h>
int min(int a,int b)
{
return a<b?a:b;
}
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int L,n;
int pos;
scanf("%d%d",&n,&L);
int minT=0,maxT=0;
for (int i=1;i<=n;i++)
{
scanf("%d",&pos);
minT=max(minT,min(pos,L+1-pos));
maxT=max(maxT,max(pos,L+1-pos));
}
printf("%d %d\n",minT,maxT);
return 0;
}
習題56
56-1 又是螞蟻
問題描述
有N只螞蟻在一根無限長的木棍上，每一只螞蟻都有一個初始位置和初始朝向（任意兩只螞蟻的初始位置不同），螞蟻們以每秒一個單位的速度向前移動，當兩只螞蟻相遇時，它們會掉頭（掉頭時間忽略不計），現給出每只螞蟻的初始位置和初始朝向，請計算出它們在t秒后的位置和朝向，
輸入格式
第一行，兩個空格隔開的整數n，t（代表螞蟻數n和時間t，n<=100000，t<=100000）；
第2~n+1行每行兩個整數，第i+1行代表第i只螞蟻的初始位置ai（ai的絕對值在1000000以內）及初始朝向bi（bi=1時螞蟻朝右，bi=-1時螞蟻朝左），
輸出格式
n行，每行兩個整數，第i行代表t秒后第i只螞蟻的位置及朝向（-1表示朝左，1表示朝右，0表示正在轉向中），
輸入樣例
4 1
1 1
5 1
3 -1
10 1
輸出樣例
2 0
6 1
2 0
11 1
（1）編程思路，
按例56的思路，每只螞蟻每次遇到別的螞蟻后就不斷變身，那么就相當于每只螞蟻是獨立運動的，因此每只螞蟻只管初始狀態和最終狀態，只是處理好相遇變身問題即可，
為此定義一個結構體struct Node來表示每只螞蟻，該結構體包括3個成員，分別表示螞蟻的位置、方向和編號，
定義兩個結構體陣列struct Node q[100005],p[100005]; ，其中陣列q用來保存初始狀態，陣列p用來保存最終狀態，將初始狀態陣列按位置從小到大排序后，將每只螞蟻按位置的相對關系保存到映射陣列order中，其中order[i]的值表示排在第i個位置的螞蟻，
因為不管兩只螞蟻相遇后如何轉身，兩只螞蟻的相對位置關系一定不會發生變化，
例如，有A，B兩只螞蟻相遇，相遇前狀態為A---> <---B，螞蟻A向右走，螞蟻B向左走，相遇轉身后的狀態為<---A B--->，螞蟻A向左走，螞蟻B向右走，即不管A，B兩只螞蟻中間如何相遇轉身，兩種螞蟻的相對位置關系一定不變，因此，初始狀態下各螞蟻在按位置從小到大序列中的排名，與在最終狀態下按位置從小到大序列中的排名一定一樣，這樣，N只螞蟻按例56那樣看成每只螞蟻獨立運動可得到N個最終狀態，再將最終狀態陣列按位置從小到大排序，再按映射陣列對應的關系，輸出各螞蟻最終的位置和方向即可，在最終狀態中，若兩只螞蟻位置相等，注意處理一下其方向即可，
（2）源程式，
#include <stdio.h>
struct Node
{
int s; // 位置
int h; // 方向
int num; // 螞蟻編號
};
struct Node q[100005],p[100005]; // q用來保存初狀態，p用來保存末狀態
void mysort(struct Node a[],int n)
{
int i,j;
struct Node t;
for (i=1;i<n;i++)
for (j=1;j<=n-i;j++)
if (a[j].s>a[j+1].s)
{
t=a[j]; a[j]=a[j+1]; a[j+1]=t;
}
}
int order[100005];
int main()
{
int n,t;
scanf("%d%d",&n,&t);
int i;
for (i=1;i<=n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
q[i].s=a;
q[i].h=b;
q[i].num=i;
p[i].s=a+b*t; // t的正負代表了向右還是向左
p[i].num=0; // 對于p陣列是用來通過order的映射輸出的所以不需要
p[i].h=b;
}
mysort(q,n);
for (i=1;i<=n;i++)
{
order[q[i].num]=i; // 從左到右的螞蟻編號映射成sort后對應的下標
}
mysort(p,n);
for (i=1;i<=n;i++)
{
if (p[i].s==p[i+1].s) // 正在相遇轉向
{
p[i].h=0;
p[i+1].h=0;
}
}
for (i=1;i<=n;i++)
{
int g=order[i];
printf("%d %d\n",p[g].s,p[g].h);
}
return 0;
}
56-2 還是螞蟻
問題描述
在東西排布的兩棵樹之間懸掛著一條長為L的細繩，有N只螞蟻在這條繩上，這些螞蟻希望通過繩子爬到任何一棵樹上，但這條繩太細了，導致兩只螞蟻不能并排爬行，也不能交錯而過，
它們想到了一個方法：每只螞蟻都以每單位時間移動一個單位距離的速度不斷向前爬，當迎面碰到另一只螞蟻時，兩只螞蟻都將立即掉頭并繼續向前爬，現在，螞蟻們想知道自己是否能爬下繩子，如果能，它們還希望知道自己爬下繩子所花的時間，為了方便，我們按初始時位置從東到西的順序對螞蟻從1開始編號，
輸入格式
輸入的第一行包含兩個正整數 N, L，保證N≤105 ,L≤109，且 N<L，
輸入的第二行包含N個正整數，第i 個數pi表示第i只螞蟻到東側樹木的距離，保證pi隨i增大嚴格遞增，且 0<pi <L，
輸入的第三行包含N個整數，第i個數di若為1則表示第i只螞蟻一開始朝向西側，為0則表示朝向東側，
輸出格式
輸出僅一行，包含N個數，第i個數表示第i只螞蟻爬下繩子所花時間，四舍五入保留到整數，若第i只螞蟻無法爬下繩子，則輸出的第i個數為?1，
輸入樣例
3 6
1 3 5
1 1 0
輸出樣例
5 5 3
樣例解釋
第三只螞蟻在爬行1 個單位時間后遇見第二只螞蟻并掉頭，再爬行2個單位時間到西側樹木；
第二只螞蟻在爬行1 個單位時間后遇見第三只螞蟻并掉頭，再爬行1 個單位時間后遇見第一只螞蟻并掉頭，再爬行3 個單位時間到西側樹木；
第一只螞蟻在爬行2 個單位時間后遇見第二只螞蟻并掉頭，再爬行3 個單位時間到東側樹木，
（1）編程思路，
按例56和習題56-1的思路，可以有如下觀點：
1）每只螞蟻每次遇到別的螞蟻后就不斷變身，那么就相當于每只螞蟻是獨立運動的，
2）不管兩只螞蟻相遇后如何轉身，兩只螞蟻的相對位置關系一定不會發生變化，
另外，n只螞蟻中，設初始時x只螞蟻向東爬，y只螞蟻向西爬，任何一次相遇轉身后，原來向東爬的螞蟻向西爬，原來向西爬的螞蟻向東爬，也就是一次相遇轉身不會增加向東爬的螞蟻只數，也不會增加向西爬的螞蟻只數，這樣，最終狀態一定是前x只螞蟻向東爬，后y只螞蟻向西爬，前x只向東爬的螞蟻可以看成是原來向東爬的x只螞蟻的獨立運動（相遇變身），
這樣，問題就簡單了，先回圈輸出向東爬的螞蟻的爬行距離pi，再回圈輸出向西爬的螞蟻的爬行距離L-pi，
（2）源程式，
#include <stdio.h>
int main()
{
int a[100005],st[100005];
int n,l;
scanf("%d%d",&n,&l);
int i;
for (i=1;i<=n;i++)
scanf("%d",&a[i]);
for (i=1;i<=n;i++)
scanf("%d",&st[i]);
for (i=1;i<=n;i++)
{
if (st[i]==0)
{
printf("%d ",a[i]);
}
}
for (i=1;i<=n;i++)
{
if (st[i]==1)
{
printf("%d ",l-a[i]);
}
}
return 0;
}
56-3 直線上行走
問題描述
給定一條直線，長度為L ，用區間表示為[0, L]，在直線上有N個人，每個人有一個初始位置pos（用到直線上端點0的距離表示）和初始方向dir（'p' 或 'P' 表示向端點L行走， 'n'或'N'表示向端點0行走），然后所有的人都開始沿著自己的方向用相同的速度v行走，若走到端點0或端點L，則此人掉下去；若兩個方向相反的人碰到一起，則分別掉頭，繼續行走（速度不變），
求出最后掉下去的人和掉下去的時間，
輸入
輸入包括多組測驗用例，每組測驗用例的格式描述如下：
第1行包括一個整數（N<32000），N=0表示輸入的結束，
第2行包含兩個浮點數，長度L和速度V，
在接下來的N行中，每行包括三個資料 DIR POS NAME，其中
POS：每個人的初始位置（0<=POS<=L），初始位置已按從小到大排列，
DIR：每個人的初始行走方向，“p”或“P”表示正方向，“n”或“N”表示負方向，
NAME：行走者的姓名（最多250個字符），
輸出
每個測驗用例的輸出由一行組成，該行第一個值是最后一個掉下去的人的掉下時間，該值輸出寬度為13且保留兩位小數，第二個值是最后一個掉下去的人的姓名，兩者之間使用單個空格字符分隔，
輸入樣例
1
13.5 2
p 3.5 Smarty
4
10 1
p 1 Helga
n 3 Joanna
p 5 Venus
n 7 Clever
0
輸出樣例
5.00 Smarty
9.00 Venus
（1）編程思路，
由于相遇只是交換方向，速度不變，因此可以視為兩個人只是“擦肩而過”，各自的速度方向均未發生變化，這樣轉換之后的整體的效果和之前的整體的效果是一樣的，那么，求最后掉下的時間就可以直接求每個人走到各自方向的端點所需要的時間，然后求最大值即可，此時，設掉下去時間最大的人為A，
如何求最后掉下去的人是誰呢？最后掉下去的人肯定是和A相遇轉身過的人一直不停的相遇轉身的最后一個人，即，若A和B相遇，之后B又和C相遇，之后C又和…的最后一個人，
由于N個人的初始位置按從小到大，這樣從A開始，沿著A的行走方向的與A的方向相反的第count個人，就是最后和A碰撞之后的人碰撞的那個人，也就是最后掉下去的人，
（2）源程式，
#include <stdio.h>
struct Node
{
int dir;
double pos;
char name[255];
};
struct Node person[32005];
int main()
{
int n;
while (scanf("%d",&n) && n)
{
double l, v;
scanf("%lf%lf",&l,&v);
char dir[3];
int i;
for (i = 0; i<n; i++)
{
scanf("%s %lf %s",dir,&person[i].pos,person[i].name);
person[i].dir = ((dir[0] == 'p' || dir[0] == 'P')? 0 : 1);
}
double max_t = 0;
int max_id;
for (i = 0; i < n; i ++)
{
if (person[i].dir == 1)
{
if (max_t < person[i].pos / v)
{
max_t = person[i].pos / v;
max_id = i;
}
}
else
{
if (max_t < (l - person[i].pos) / v)
{
max_t = (l - person[i].pos) / v;
max_id = i;
}
}
}
int count = 0;
int id = 0;
if (person[max_id].dir == 0)
{
for (i = max_id + 1; i < n; i++)
{
if (person[i].dir == 1)
{
count++;
}
}
id = max_id + count;
}
else
{
for (i = 0; i<max_id; i++)
{
if (person[i].dir == 0)
{
count++;
}
}
id = max_id - count;
}
printf("%13.2f %s\n", (int)(max_t*100)/100.0, person[id].name);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/421289.html
標籤：C