每日一练|蚂蚁问题每日一练（一）每日一练|C

总结：1.结构体到底怎么用？
2.函数调用，调用函数中的返回值如何打印出来在主函数，前面讲过可以在调用函数中打印，但是当无法在调用函数中打印，而且打印函数不止一个时，又不能用return只能返回一个。

bar( L, T, N, s ); //关键的函数调用程序，注意对应voidbar( int L, int T, int N, struct foo s[] )
//实参给形参，调用函数把实参复制一份传送给调用函数的形参，实现数据传递
//调用函数对一些非实参和形参产生的影响可以在main函数中应用，形参会在函数调用结束后消失，main函数中定义的 //比如这里的结构体s不会消失，调用函数对它的改变有效，并且不会在函数调用后消失。另外，实参也不会改变
也就是说之前说的函数调用有两个返回值时，可以现在main函数中定义这两个数据，然后在调用函数中去赋值就行。总之，调用函数不能返回形参，其他main函数中定义的变量都会运行并且保存。

一根长度为L厘米的木棍上有n只蚂蚁，每只蚂蚁要么朝左爬，要么朝右爬，速度为1厘米/秒。当两只蚂蚁相撞时，二者同时掉头（掉头时间忽略不计）。给出每只蚂蚁的初始位置和朝向，计算T秒之后每只蚂蚁的位置。

输入格式：
输入的第一行为数据组数。每组数据的第一行为3个正整数L、T、n（0<=n<=10000）；以下n行每行描述一只蚂蚁的初始位置，其中，整数x为蚂蚁距离木棍左端的距离（单位：厘米），字母表示初始朝向（L表示朝左，R表示朝右）。
输出格式：
对于每组数据，输出n行，按输入顺序输出每只蚂蚁的位置和朝向（Turing表示正在碰撞）。在第T秒之前已经掉下木棍的蚂蚁（正好爬到木棍边缘的不算）输出Fell off。

样例输入：
2
10 1 4
1 R
5 R
3 L
10 R
10 2 3
4 R
5 L
8 R
样例输出：
Case #1:
2 Turing
6 R
2 Turing
Fell off

Case #2:
3 L
6 R

10 R
抽烟归来，为了便于理解，我举个例子吧
假设一开始从左到右分别是 4R 5L 8R ----------- 序列1
若不考虑碰撞，2秒后分别变为 6R 3L 10R ------- 序列2
将 6R 3L 10R 从左到右排序，变为 3L 6R 10R --- 序列3
将序列1和序列2一一对应，可知 4R变成了3L、5L变成了6R、8R变成了10R
整个算法的核心就是一个简单的排序

#include #include #include struct foo { int inputorder; int position; char direction; }; int compare1( const void* a, const void* b ) { return (*(const struct foo*)a).position - (*(const struct foo*)b).position; //对位置 } int compare2( const void* a, const void* b ) { return (*(const struct foo*)a).inputorder - (*(const struct foo*)b).inputorder; // }void bar( int L, int T, int N, struct foo s[] ) { qsort( s, N, sizeof(s[0]), &compare1 ); ///以结构体的位置为排序参考进行排序，整个结构体是三个数据，第几个蚂蚁、位置、方向都要变struct foo s2[10000]; memcpy( s2, s, N*sizeof(s[0]) ); ///复制结构体数组s给s2，留在判断是否碰撞处判断用 for( int i=0; i!=N; ++i ) s[i].position = s[i].direction=='L' ? s[i].position-T : s[i].position+T; qsort( s, N, sizeof(s[0]), &compare1 ); ///T秒后各自的位置快速排序，不考虑碰撞的情况下，整个进行排序for( int i=0; i!=N; ++i ) { s[i].inputorder = s2[i].inputorder; //由于之前快速排序是整个的结构体排序，将蚂蚁A、B、C打乱了，最后的记过肯定还是蚂蚁A、B、C排序(题目要求)，if( s[i].position<0 || s[i].position>L )//故有第三个按照蚂蚁标志进行的快速排序 s[i].direction = 'F'; else if( i!=N && s[i].position==s[i+1].position ) s[i].direction='T', s[i+1].direction='T'; }qsort( s, N, sizeof(s[0]), &compare2 ); ///故有第三个按照蚂蚁标志进行的快速排序 }int main() { int cnt; scanf( "%d", &cnt ); for( int idx=0; idx!=cnt; ++idx ) { int L, T, N; scanf( "%d%d%d", &L, &T, &N ); struct foo s[10000]; //s是结构体数序的首地址 for( int i=0; i!=N; ++i ) { s[i].inputorder = i; scanf( "%d %c", &s[i].position, &s[i].direction ); }bar( L, T, N, s ); //关键的函数调用程序，注意对应void bar( int L, int T, int N, struct foo s[] )

//实参给形参，调用函数把实参复制一份传送给调用函数的形参，实现数据传递

//调用函数对一些非实参和形参产生的影响可以在main函数中应用，形参会在函数调用结束后消失，main函数中定义的 //比如这里的结构体s不会消失，调用函数对它的改变有效，并且不会在函数调用后消失。另外，实参也不会改变 printf( "Case #%d:\n", idx+1 ); for( int i=0; i!=N; ++i ) { switch( s[i].direction ) ///函数调用过程中，
{ case 'F': printf( "Fell off\n" ); break; case 'T': printf( "%d Turing\n", s[i].position ); break; default: printf( "%d %c\n", s[i].position, s[i].direction ); break; } } printf( "\n" ); } return 0; }

【每日一练|蚂蚁问题每日一练（一）】