mxqz
查看原帖
mxqz
341353
封禁用户楼主2022/10/3 22:01

萌新求助 CSP2019T2 公交换乘

太丢人了,调了半个小时,样例都过,但是全WA,#16T

变量含义:

  1. trip记录每一条输入信息
  2. tot是总花费
  3. ticket是目前的优惠券,fuse是目前第一张可以用的券,has是一共的优惠券,包括用过的,stoptime的first表示截止时间,second表示产生这一张优惠券的地铁旅程价格
  4. flag表示找到可用优惠券
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;

int n;
int tot=0;
struct record{
	bool type;
	int cost, tim;
}trip[maxn];

struct tic{
	int fuse=1;
	int has=0;
	pair <int, int> stoptime[maxn]; // first->stoptime second->price
}ticket;

int main(){
	cin>>n;
	for (int i=1; i<=n; i++)
		cin>>trip[i].type>>trip[i].cost>>trip[i].tim;
		
	for (int i=1; i<=n; i++){
		if (!trip[i].type) ticket.has++, ticket.stoptime[ticket.has].first=trip[ticket.has].tim+45, ticket.stoptime[ticket.has].second=trip[ticket.has].cost, tot+=trip[i].cost;
		else{
			if (trip[i].tim>ticket.stoptime[ticket.fuse].first && ticket.stoptime[ticket.fuse].first) tot+=trip[i].cost;
			else{
				bool flag=false;
				for (int j=1; j<=ticket.has; j++)
					if (!flag && ticket.stoptime[j].first && ticket.stoptime[j].first>=trip[i].tim && ticket.stoptime[j].second>=trip[i].cost)
						{ ticket.stoptime[j].first=0, ticket.stoptime[j].second=0, ticket.fuse++; flag=true; }
				if (!flag) tot+=trip[i].cost;
			}
		}
	}
	cout<<tot<<endl;
	return 0;
}
/*
6
0 10 3
1 5 46
0 12 50
1 3 96
0 5 110
1 6 135 
*/ 
2022/10/3 22:01
加载中...