首页 > 试题广场 >

火车票订购

[编程题]火车票订购

热度指数：5092 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

火车经过X站，火车最大载客人数为m，有n个订票请求，请求订购从a站到b站的k张票，若能满足订购要求则输出1，否则输出0。

输入描述:

输入包含多组测试数据。

每组第一行输入两个数，分别为n，m。接下来有n行，每行三个数分别为a，b，k。

输出描述:

输出相应的结果表示能否满足订购要求。

示例1

输入

输出

算法知识视频讲解

~201809031649432

#include<stdio.h>
int main(){
int n,m;
int s[1001]={0};
int tmp[1001]={0};
while(scanf("%d %d",&n,&m)!=EOF){
while(n--){
int a,b,k,cout;
cout=0;
scanf("%d %d %d",&a,&b,&k);
for(int i=a;i<=b;i++){
s[i]+=k;
}
for(int j=a;j<=b;j++){
if(s[j]>m){
cout=1;
for(int x=a;x<=b;x++)
s[x]=tmp[x];
printf("0\n");
}
}
if(cout==0){
for(int y=a;y<=b;y++)
tmp[y]=s[y];
printf("1\n");}
}
}
return 0;

}

有没有大佬帮忙看看为什么数组越界了？

发表于 2019-03-01 16:29:23 回复(5)

C++

会时Kk

啊这,本来想用数组解决的,但给的区间这么大,一看要用线段树

,咱也不去竞赛啊.

发表于 2023-03-03 22:09:56 回复(0)

upc_llk

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <string>
#include <map>

using namespace std;

struct P {
	int starttime, endtime, peoplenum;
	bool operator<(const P& x)const {
		return  endtime > x.endtime;
	}
};

int main()
{
	int people, remain;
	while (scanf("%d%d", &people, &remain) != EOF) {
		vector<int>result;
		priority_queue<P>que;
		while (people--) {
			P temp;
			scanf("%d%d%d", &temp.starttime, &temp.endtime, &temp.peoplenum);
			//cin >> temp.starttime >> temp.endtime >> temp.peoplenum;
			if (temp.peoplenum <= remain) {
				que.push(temp);
				remain -= temp.peoplenum;
				result.push_back(1);
			}
			else if (!que.empty()) {
				P tag = que.top();
				while (!que.empty() && tag.endtime <= temp.starttime) {
					remain += tag.peoplenum;
					que.pop();
					if (!que.empty()) {
						tag = que.top();
					}
				}
				if (temp.peoplenum <= remain) {
					que.push(temp);
					remain -= temp.peoplenum;
					result.push_back(1);
				}
				else
					result.push_back(0);
			}
			else
				result.push_back(0);
		}
		for (int i : result)
			printf("%d\n", i);
	}
}

执行结果：答案错误:您提交的程序没有通过所有的测试用例用例通过率: 74.25% 运行时间: 235ms 占用内存: 2524KB

用例输入 324699 721496 356

用例输出 1

实际输出 0

=_=

发表于 2020-08-08 22:24:04 回复(0)

好的名字让你记住我

本地跑没问题，超时不知道如何修正

while True:
    try:
        n,m=map(int,input().split())
        mtx=[]
        for i in range(n):
            l=list(map(int,input().split()))
            mtx.append(l)
        a,b,sum=0,0,0
        for i in range(n):
            flg=0
            tmp0,tmp1,tmp2=mtx[i][0],mtx[i][1],mtx[i][2]    
            if tmp0<b:
                if (sum+tmp2)<=m:
                    sum,flg,a,b=sum+tmp2,1,tmp0,max(b,tmp1)
            else:
                if tmp2<=m:
                    sum,flg,a,b=tmp2,1,tmp0,tmp1
            print(flg)
    except:
        break

编辑于 2020-07-31 11:43:55 回复(0)

Rolay

#include <stdio.h>
(737)#include <string.h>
#include <queue>
(789)#include <vector>
#include <iostream>
(720)#include <algorithm>
#include <stack>
(850)#include <list>
#include <map>
(747)#include <math.h>
using namespace std;
#define MIN -0x7fffffff
(3237)#define MAX 0x7fffffff
//这一题我的思路是把每个购票信息分成一个个的时间节点。这样，一条信息我们就可以拆分为两条信
//息，也就是两个时间节点。一个上车信息，一个下车信息。同时为了在下车时对应其上车时的购票
//数，我又用ID来唯一标识每一个购票记录。
//存储时间节点信息
struct Time_Node{
    int id;  // 标识唯一的购票记录
    int time;  // 时间点
    int flag;  // 时间点类型，1表示上车，-1表示下车
    int ticket_sum;  // 票数
    bool operator < (const Time_Node &A) const{  // 按照时间顺序依次进行，且在同一时间点下车在上
//车后
        if(time != A.time)
            return time < A.time;
        else
            return flag < A.flag;
    }
}sample[10001];  // 题目有点坑，N的值非常大，所以我把数组开到1000001
vector<int> q;  // 存储成功上车的ID标识符
vector<int>::iterator it;
int size;
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m) != EOF){
        int a,b,k;
        size = 0;
        while(!q.empty())
            q.pop_back();
        for(int i=0;i<n;i++){
            scanf("%d%d%d",&a,&b,&k);
            // 上车信息
            sample[size].id = i;
            sample[size].time = a;
            sample[size].flag = 1;
            sample[size++].ticket_sum = k;
            // 下车信息
            sample[size].id = i;
            sample[size].time = b;
            sample[size].flag = -1;
            sample[size++].ticket_sum = k;
        }
        //printf("size=%d\n", size);
        sort(sample,sample+size);  // 排序
        int currentTime = 0;  // 当前时间
        int currentTicket = 0;  // 当前已购票数
        for(int i=0;i<size;i++){
            if(sample[i].flag == 1){  // 若是上车节点信息
                if(currentTicket + sample[i].ticket_sum <= m){  // 还能上车
                    q.push_back(sample[i].id);
                    currentTicket += sample[i].ticket_sum;
                    printf("1\n");
                }
                else{
                    printf("0\n");
                }
            }
            else{  // 若是下车信息
                for(it=q.begin();it!=q.end();it++){
                    if(*it == sample[i].id){  // 若此下车信息是之前上车信息中所记录的
                        currentTicket -= sample[i].ticket_sum;
                        q.erase(it);  // 消除此上车记录
                        break;
                    }
                }
            }
            //printf("currentTicket=%d\n", currentTicket);
        }
    }
    return 0;
}

美中不足的是只过了样例的74.15%，本人想了许久，没有想出来究竟为什么错了，希望大家看出来的务必一起讨论，一起进步

发表于 2020-04-03 10:31:39 回复(3)

C/C++

kevindebury

本地IDE没问题，但是牛客出现下面情况？？？？

本地IDE：

还是贴一下代码吧：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//这一题的意思就是，中间站有人订票但是这时这个站火车上已经有人，且总人数大于最大载客人数，则返回0。
bool solve(int m,int k,vector<int>&ans,int a,int b){
    if(k>m)return false;
    for(int i=a;i<b;i++)
        if((ans[i]+k)>m)
            return false;
    return true;
}
int main(){
    int n,m,a,b,k;
    cin>>n>>m;
    vector<int>ans(10086,0);
    while(n--){
        cin>>a>>b>>k;
        /*for(int i=a;i<b;i++){
            ans[i]+=k;
        }*///注意只有满足条件的,才进行for循环的操作
        if(solve(m,k,ans,a,b)==false)
            cout<<"0"<<endl;
        else{
            for(int i=a;i<b;i++)
                ans[i]+=k;
            cout<<"1"<<endl;
        }
    }
    
    
    return 0;
}

发表于 2020-02-08 02:02:31 回复(5)

顾子zz

#include<iostream>
using namespace std;
#define MAX 1000

int num[MAX];

bool isFull(int a,int b,int k,int m){
    if(k>m)return true;
    for(int i=a;i<b;i++){
        if((num[i]+k)>m)return true;
    }
    return false;
}

int main(){
    int m,n,a,b,k;
    while(cin>>n>>m){
        for(int i=0;i<MAX;i++)num[i]=0;
        for(int i=0;i<n;i++){
            cin>>a>>b>>k;
            if(isFull(a,b,k,m))cout<<"0\n";
            else{
                for(int j=a;j<b;j++)num[j]+=k;
                cout<<"1\n";
            }
        }
    }
    return 0;
}

发生段错误或数组越界。。

发表于 2019-09-08 10:01:39 回复(0)

磊*

#include<stdio.h>

int train(int s[],int q,int w,int e,int m);

int main()
{
    int n,m,a,b,k;
    int s[1000] = {0};
    int j[20]={0},l,t=0;
    scanf("%d%d",&n,&m);
    for(;n>0;n--)
    {
        scanf("%d%d%d",&a,&b,&k);
        l=train(s,a,b,k,m);
        j[t++]=l;
    }
    for(l=0;l<t;l++)
        printf("%d\n",j[l]);

    return 0;
}

int train(int s[],int q,int w,int e,int m)
{
    int i = 0;
    for(i = q-1;i <= w-1;i++)
    {
        s[i] = s[i]+e;
        if(s[i] > m)
        {
        for(i = w-1;i >= q-1;i--)
            s[i] = s[i]-e;
        return 0;
        }
    }
    return 1;
}

本地跑贼6，自测都通过了，就是不对

发表于 2019-07-25 23:04:38 回复(0)

ashoka

您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为0.00%

用例:
4 10 9

对应输出应该为:

0

你的输出为:

这什么鬼啊！？

发表于 2019-06-26 21:36:29 回复(0)

风雨也从容

//本地跑贼溜😂

#include<bits/stdc++.h>

int main(void)
{
int n, m;
scanf("%d%d", &n, &m);
int **arr;
arr = (int**)malloc(n*sizeof(int*));
for(int i = 0; i < n; ++i) {
int local = m;
arr[i] = (int*)malloc(4*sizeof(int));
scanf("%d%d%d", arr[i]+1, arr[i]+2, arr[i]+3);
for(int j = i - 1; j >= 0 && arr[i][1] < arr[j][2]; --j) {
if(arr[j][0])
local -= arr[j][3];
}
if(local < arr[i][3]) {
printf("0\n");
arr[i][0] = 0;
} else {
printf("1\n");
arr[i][0] = 1;
}
}
return 0;
}

发表于 2019-04-29 23:02:03 回复(0)

Aroone

#include <iostream>

#include <vector>

using namespace std;

int judge ( int m , vector<int>station ){

for ( int i = 0 ; i < station.size() ; i ++ ){

if ( station[i] > m ){

return 0;

}

return 1;

}

int main(){

int n , m ;

//cout << "in: ";

while ( cin >> n ){

vector<int>station ( 100, 0 );

cin >> m;

for ( int i = 0 ; i < n ; i++ ){

int a, b, k;

cin >> a >> b >> k;

if ( b > station.size() ){

for ( int p = station.size() ; p < b ; p++ ) {

station.push_back(0);

}

for ( int j = a-1 ; j < b ; j++ ){

station[j] += k;

}

cout << judge( m , station ) << endl;

if ( !judge( m , station) ){

for ( int j = a-1 ; j < b ; j++ ){

station[j] -= k;

}

本地能跑

求助超内存了咋整呀？

发表于 2019-03-22 16:35:53 回复(0)

沉默着

到底是用了多大的数。。

不通过

您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为14.74%
用例:
463426784 999969204 415
对应输出应该为:
1
你的输出为:
空.请检查一下你的代码，有没有循环输入处理多个case.

发表于 2019-03-22 14:57:03 回复(0)

皮蛋秀柚秋

欸。。我好菜啊连题目意思都看不懂了

发表于 2019-03-18 17:00:52 回复(0)

C/C++

乘风破浪2022

#include<iostream>
using namespace std;

int main()
{
int N,M;
int b[10000];
while(cin>>N>>M)
{
for(int i=0;i<10000;i++)
b[i]=M;
int a[100][3];
for(int i1=0;i1<N;i1++)
{int x,y,z;
cin>>x>>y>>z;
a[i1][0]=x;
a[i1][1]=y;
a[i1][2]=z;}
for(int i4=0;i4<N;i4++)
{int flag=0;
for(int i2=a[i4][0]+1;i2<a[i4][1];i2++)
if(a[i4][2]>b[i2]) {flag=1;break;}
if(flag==1) cout<<'0'<<endl;
else if(flag==0) {for(int i3=a[i4][0]+1;i3<a[i4][1];i3++) b[i3]=b[i3]-a[i4][2];cout<<'1'<<endl;}
}
}
return 0;
}

编辑于 2019-03-01 09:13:24 回复(1)