201809-2. 买菜
解题思路：
主要就是判断小H和小W的装车时间段是否有重叠区间。关于判断重叠区间，对于给定的两个区间(a,b)和(c,d),显然当且仅当a≤d且b≥c时才会有重叠区间，而重叠区间长度L为min(b,d)-max(a,c)，把所有重叠区间的长度进行累加求和，就可以知道俩人可以聊多长时间。
100分代码：
1 #include2 using namespace std; 3 4 void Input(int a[][2],int n); //用来输入装车时间 5 6 int main() 7 { 8 int n; 9 cin >> n; //时间段的数量10 int H[n][2]; //小H的各个装车的时间段11 Input(H,n);12 int W[n][2]; //小W的各个装车的时间段13 Input(W,n);14 int ans = 0;15 for (int i = 0; i < n; i++)16 {17 for (int j = 0; j < n; j++)18 {19 //对于给定的两个区间(a,b)和(c,d),显然当且仅当a≤d且b≥c时才会有重叠区间20 if(H[i][0]<=W[j][1]&&H[i][1]>=W[j][0]) //判断有无重叠区间21 {22 //重叠区间长度L为min(b,d)-max(a,c)23 ans += min(H[i][1],W[j][1])-max(H[i][0],W[j][0]); //加上重叠区间24 }25 }26 }27 cout << ans << endl;28 return 0;29 }30 31 void Input(int a[][2],int n)32 {33 for (int i = 0; i < n; ++i)34 {35 cin >> a[i][0] >> a[i][1];36 }37 }
201803-2. 碰撞的小球
解题思路：
先吐槽一波，这道物理题也太长了吧，我截了3张图再把它们用photoshop拼起来的。建立俩个数组分别用来存取小球的位置和方向(规定方向向右为1，向左为-1)。每秒每个小球移动一个单位长度，小球每次移动之后都需要判断①该小球是否和其他小球发生碰撞，若发生了碰撞则碰撞的俩者都要改变方向；②该小球是否到达边界，若到达了边界也改变方向。最后输出每个小球的位置即可。
100分代码：
1 #include2 using namespace std; 3 4 int main() 5 { 6 int N,L,T; //N为小球的个数,L为线段长度,计算T秒后小球的位置 7 cin >> N >> L >> T; 8 int a[N]; //n个小球的位置 9 int b[N]; //n个小球的方向10 for (int i = 0; i < N; i++)11 {12 cin >> a[i];13 b[i] = 1; //规定向右为1,向左为-114 }15 while(T--)16 {17 for (int i = 0; i < N; i++)18 {19 a[i] += b[i]; //每个位置每次移动一个单位长度20 }21 for (int i = 0; i < N; i++)22 {23 for (int j = i+1; j < N; j++) //判断小球是否和其他小球发生碰撞,若碰撞了则俩者均改变方向24 {25 if(a[i]==a[j])26 {27 b[i] = -b[i];28 b[j] = -b[j];29 }30 }31 if(a[i]==0||a[i]==L) //判断小球是否到达边界,若到达边界则改变方向32 {33 b[i] = -b[i];34 }35 }36 }37 for (int i = 0; i < N; i++)38 {39 cout << a[i] << " ";40 }41 return 0;42 }
201712-2. 游戏
解题思路：
这是一个约瑟夫环问题，我用队列来实现的。n个小朋友依次入队(假设围成了一个圈)，count为计数器(用来记录报数)。排在队首的小孩报的数若是k的倍数或其个位数为k，则将该小孩淘汰。若小孩没有被淘汰则把他放入队尾继续转圈报数。
100分代码：
1 #include2 using namespace std; 3 4 bool Out(int count,int k) //判断小孩是否被淘汰 5 { 6 if(count%k==0||count%10==k) //若一个小朋友报的数为k的倍数或个位数为k 7 { 8 return true; //将该小孩淘汰出局 9 }10 return false;11 }12 13 int main()14 {15 int n,k;16 cin >> n >> k;17 queue q;18 int count = 0; //计数器19 for (int i = 1; i <= n; i++) 20 {21 q.push(i); //n个小朋友依次入队22 }23 while(q.size()>1)24 {25 count++;26 int temp = q.front(); //读取队首元素27 q.pop(); //删除队首元素28 if(!Out(count,k)) //若该小孩没有被淘汰,则加入队尾继续转圈报数29 {30 q.push(temp);31 }32 }33 cout << q.front() << endl;34 return 0;35 }
201709-2. 公共钥匙盒
解题思路：
先定义一个教师结构体Teacher配合vector一起使用，里面有钥匙编号、使用钥匙的时间、标识符(0借1还)，再创建一个钥匙列表key。vector先按还钥匙的时间升序排列，若还取钥匙的时间相同，则按先借后还排列，若多位老师还钥匙，则按钥匙编号升序排列。排序好以后，用for-each循环对vector进行遍历进行借还钥匙操作即可。最后对钥匙列表进行输出即可。
100分代码：
1 #include2 using namespace std; 3 4 struct Teacher 5 { 6 int key; //钥匙编号 7 int time; //使用钥匙的时间 8 int flag; //设置标识符,0借,1还 9 };10 11 bool Cmp(Teacher a,Teacher b)12 {13 if(a.time != b.time)14 {15 return a.time < b.time; //先按还取钥匙的时间升序排序16 }17 else if(a.flag != b.flag)18 {19 return a.flag > b.flag;20 }21 else //若多位老师还钥匙22 {23 return a.key < b.key; //则按钥匙编号升序排列24 }25 }26 27 int main()28 {29 ios::sync_with_stdio(false); //取消cin和stdin的同步30 int N,K;31 int key[1001]; //钥匙列表32 cin >> N >> K;33 vector v;34 for (int i = 1; i <= N; i++)35 {36 key[i] = i; //对钥匙进行赋初值37 }38 for (int i = 0; i < K; ++i)39 {40 int w,s,c; //老师要使用的钥匙编号w、开始上课的时间s和上课的时长c41 cin >> w >> s >> c;42 v.push_back({w,s,0}); //借43 v.push_back({w,s+c,1}); //还44 }45 sort(v.begin(),v.end(),Cmp); 46 for(auto it:v) 47 {48 if(it.flag == 0) //借钥匙49 {50 for (int i = 1; i <= N; i++)51 {52 if(key[i] == it.key)53 {54 key[i] = 0; //钥匙被借走了55 break;56 }57 }58 }59 else //还钥匙60 {61 for (int i = 1; i <= N; i++)62 {63 if(key[i] == 0)64 {65 key[i] = it.key; //把钥匙归还66 break;67 }68 }69 }70 }71 for (int i = 1; i <= N; i++)72 {73 cout << key[i] << " ";74 }75 return 0;76 }
201703-2. 学生排队
解题思路：
这题是利用vector来操作的，先对学生序号进行初始化，然后删除指定位置的学号，并将该指定学号插入到它的最终位置，最后对vector进行输出即可。
100分代码：
1 #include2 using namespace std; 3 4 int main() 5 { 6 int n,m;//n个学生，m次移动 7 cin >> n >> m; 8 vector v; 9 for(int i = 0; i < n; i++)10 {11 v.push_back(i+1); //初始化学生序号12 }13 for(int i = 0; i < m; i++)14 {15 int p,q;//学号p,移动q 16 cin >> p >> q;17 int j = 0;18 while(i < m)19 {20 if(v[j]==p)21 {22 v.erase(v.begin()+j);//删除指定位置的学号23 v.insert(v.begin()+j+q,p);//用insert函数将指定学号插入到最终位置。24 break;25 }26 j++;27 }28 } 29 for(int i = 0; i < v.size(); i++)30 {31 cout << v[i] << " ";32 }33 return 0;34 }
201612-2. 工资计算
解题思路：
对于这题，我这个菜鸡毫无方法可言，直接暴力破解。
100分代码：
1 #include2 using namespace std; 3 4 int main() 5 { 6 int T,S; // T为税后工资,S为税前工资 7 cin >> T; 8 if (T <= 3500) 9 {10 S = T;11 }12 else if (T <= 4955)13 {14 S = ((T - 3500) / 97) * 100 + 3500;15 }16 else if (T <= 7655)17 {18 S = (T - 4955) / 90 * 100 + 5000;19 }20 else if (T <= 11255)21 {22 S = (T - 7655) / 80 * 100 + 8000;23 }24 else if (T <= 30755)25 {26 S = (T - 11255) / 75 * 100 + 12500;27 }28 else if (T <= 44755)29 {30 S = (T - 30755) / 70 * 100 + 38500;31 }32 else if (T <= 61005)33 {34 S = (T - 44755) / 65 * 100 + 58500;35 }36 else37 {38 S = (T - 61005) / 55 * 100 + 83500;39 }40 cout << S << endl;41 return 0;42 }
201609-2. 火车购票
解题思路：
用数组a来记录每排卖出的座位数，初始化为0。立一个flag用来判断能不能买到同一排相邻的座位。若需要购入的票数p加该排卖出的座位数小于5，则说明能买到同一排的相邻座位， 将flag改为true，并输出座位号。如果不能买到同一排的相邻座位，就按座位号升序来查找空座位。
100分代码：
1 #include2 using namespace std; 3 4 int main() 5 { 6 int n; //n为购票指令的数量 7 cin >> n; 8 int a[20]; //记录每排卖出的座位数 9 memset(a,0,sizeof(a)); //全部初始化为010 while(n--)11 {12 int p; //需要购入的票数13 cin >> p;14 bool flag = false; //flag为true表示能买到同一排相邻的座位15 for (int i = 0; i < 20; i++) //假设能买到同一排的相邻座位16 {17 if(a[i]+p <= 5)18 {19 for (int j = 0; j < p; j++)20 {21 if(j != p-1)22 {23 cout << i*5+a[i]+j+1 << " ";24 }25 else26 {27 cout << i*5+a[i]+j+1 << endl;28 }29 }30 a[i] += p;31 flag = true;32 break;33 }34 }35 if(!flag) //如果不能买到同一排的相邻座位,就按座位号从小到大来寻找空座位36 {37 int num = 0;38 for (int i = 0; i < 20; i++)39 {40 if(a[i] < 5)41 {42 num++;43 if(num == p)44 {45 cout << i*5+a[i]+1 << endl;46 }47 else48 {49 cout << i*5+a[i]+1 << " ";50 }51 a[i]++;52 i--; //这一排可能还有空座位53 }54 }55 }56 }57 return 0;58 }