CSP-J-2019-公交换乘

78 阅读 0 评论 52 点赞

我是靠谱客的博主魔幻菠萝，最近开发中收集的这篇文章主要介绍CSP-J-2019-公交换乘，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

[CSP-J2019] 公交换乘 - 洛谷

解题思路：

1.首先，可以想到只有乘坐地铁才可以得到优惠券，优惠券有三个变量，票价，乘坐时间和是否使用，所以可以使用结构体，如果是乘坐的地铁，则将这三个变量输入到结构体数组中

2.如果乘坐的是公交的话，那么去结构体变量中依次查找有没有在有效期内的并且优惠券的票价是大于公交票钱并且还没有使用的优惠券，如果存在，标记优惠券失效，然后退出循环，如果没有这样的优惠券，则加上公交票钱，最后输出结果即可

#include<bits/stdc++.h>
using namespace std;
struct node{
	int price;
	int time;
	bool flag;//标记是否使用了该优惠券 
}a[100005];
int main()
{
	int n,x,y,z,num=0,sum=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x>>y>>z;
		if(x==0)
		{
			sum=sum+y;
			a[++num].price=y;
			a[num].time=z;
			a[num].flag=1;
		}//将乘坐地铁得到的优惠票加入到结构体数组中 
		else
		{
			bool flag2=0;//标记是否使用了优惠券 
			for(int j=1;j<=num;j++)
			{
				if((a[j].time+45)>=z&&(a[j].price>=y)&&(a[j].flag==1)) 
				{//如果在有效期内并且优惠券价格高于公交票
					a[j].flag=0;
					flag2=1;
					break;
				}
			}
			if(flag2==0)//如果没有使用优惠券 
			sum=sum+y;//加上公交的票钱 
		}
	}
	cout<<sum;
	return 0;
}

优化算法：

3.这种代码的做法的时间复杂度是O（n^2)的，当n很大的时候，肯定是有数据通不过的，这时候，就要想我们是在哪里浪费了时间？是在暴力搜索优惠券的数组时候，每次从1开始遍历浪费的时间，所以优化这部分时间，有题目中信息可以得出，给出的票都是按照时间顺序从小到大给的，并且不会有相同的两个乘车时间，那么我们其实在每次搜优惠券的时候，只需要从符合他有效期的第一张优惠券查找即可

4.那么在暴力搜索之前，设置一个while循环，如果a[temp].time+45<z，那么temp++，直到找到a[temp].time>=45的temp值，然后从temp到num查找即可

#include<bits/stdc++.h>
using namespace std;
struct node{
	int price;
	long long time;
	bool flag;//标记是否使用了该优惠券 
}a[100005];
int main()
{
	int n,x,y,z,num=0,sum=0,temp=1;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x>>y>>z;
		if(x==0)
		{
			sum=sum+y;
			a[++num].price=y;
			a[num].time=z;
			a[num].flag=1;
		}//将乘坐地铁得到的优惠票加入到结构体数组中 
		else
		{
			while(a[temp].time+45<z)
			temp++;//利用循环，找到那个第一个在有效期内的优惠票 
			bool flag2=0;//标记是否使用了优惠券 
			for(int j=temp;j<=num;j++)
			{
				if((a[j].price>=y)&&(a[j].flag==1)) 
				{//如果还没有使用并且优惠券价格高于公交票
					a[j].flag=0;
					flag2=1;
					break;
				}
			}
			if(flag2==0)//如果没有使用优惠券 
			sum=sum+y;//加上公交的票钱 
		}
	}
	cout<<sum;
	return 0;
}