首页 > 试题广场 >

火车票订购

[编程题]火车票订购
  • 热度指数：5901 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
火车经过X站，火车最大载客人数为m，有n个订票请求，请求订购从a站到b站的k张票，若能满足订购要求则输出1，否则输出0。

输入描述:
输入包含多组测试数据。

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


输出描述:
输出相应的结果表示能否满足订购要求。
示例1

输入

5 10
4 10 9
8 12 2
8 12 1
14 20 8
30 300 15

输出

1
0
1
1
0
算法知识视频讲解
添加回答
~201809031649432头像 ~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头像 会时Kk
啊这,本来想用数组解决的,但给的区间这么大,一看要用线段树,咱也不去竞赛啊.
发表于 2023-03-03 22:09:56 回复(0)
upc_llk头像 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头像 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头像 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头像 顾子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头像 ashoka
您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为0.00%

用例:
4 10 9

对应输出应该为:

0

你的输出为:

1
这什么鬼啊！？
发表于 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头像 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头像 乘风破浪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)
提交观点

问题信息

贪心 思维
上传者：小小
难度：
14条回答 6221浏览

热门推荐

通过挑战的用户

查看代码

相关试题

火车票订购

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号