中科大上机题——火车票订购
中科大上机题——火车票订购
作者：ME！
题目描述：
火车票订购：火车经过x站，火车最大载客人数为m，有n个订票请求，请求订购从a站到b站的k张票，若能满足订购要求则输出1，否则输出0，第一行有两个数，分别是n，m，接下来有n行，每行三个数分别为a，b，k。
Sample Input：
5 10
4 10 9
8 12 2
9 12 1
14 21 8
30 300 15
Sample Output：
1
0
1
1
0
算法思想：
采用线性表表示订票，每3个单位表示起点，终点以及上车的人数，那么存在两三种情况：
若第一站上车的人数大于火车承载量，那么返回失败，并且不载客；
若第一站上车的人数小于火车承载量，那么可以分成两种情况：
（1）第二站与第一站存在交叉，那么第二站能够上的人数为总人数减去第一站的人数
（2）第二站与第一站不存在交叉点，那么第二站能上的总人数为火车的容量。
#include
using namespace std;
void check(int arr[], int n, int m) {
//订单数
int count = n / 3;
//b[]用来记录每个订单的上车人数
int* b = new int[count];
for (int i = 0;i m) {//此时不载这个站的乘客
cout << 0 << endl;
restNum = m;
count--;
i++;
continue;
}
else if (i == 0) {
cout << 1 < arr[3 * i - 2]) {//不存在交叉点
for (int j = 0;j m)
restNum = m;
if (b[i] > restNum) {
cout << 0 << endl;
count--;
i++;
continue;
}
else {
cout << 1 < restNum) {
cout << 0 << endl;
count--;
i++;
continue;
}
else {
cout << 1 << endl;
restNum -= b[i];
count--;
i++;
continue;
}
}
}
}
int main() {
int n, m;
cout <> n;
cout <> m;
int* arr = new int[3 * n];//arr[0],arr[3]....表示起点站，arr[1],arr[4]..表示终点站，arr[2],arr[5]表示上车人数
for (int i = 0;i > arr[i];
check(arr, 3 * n, m);
return 0;
}
运行测试结果：
作者：ME！
