2019年Noip普及组复赛第二题解析

题目如下:

简单说一下我的思路,边输入边比较,地铁就直接把钱存入sum中,地铁的其他数据存入数组中,公交车就开始遍历我刚刚存入的数组,找到满足各种条件之后的数据(这也是我时间爆的一个原因),若能用优惠券则标识符改变。遍历结束,没有改变标识符的公交车就收钱(存入sum中)。

后面的处理方式是逆序遍历,遇到超过45min的就break掉,时间上就OK了。

给大家两种风格的代码:

一:

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100005;
struct Ticket
{
	int time, price; q[N];
}
int vis[N];
int main()
{
	int n;
	scanf("%d", &n);
	
	int ans = 0, l = 0, r = 0;
	for (int i = 0; i < n; i++)
	{
		int type, price, time;
		scanf("%d%d%d", &type, &price, &time);
		if (type == 0)
		{
			q[r++] = {time, price};
			ans += price;
		}
		else
		{
			while (l < r && time - q[l].time > 45) l++;
			
			int success = 0;
			for (int j = l; j < r; j++)
			{
				if (!vis[j] && q[j].price >= price)
				{
					vis[j] = 1;
					success = 1;
					break;
				}
			}
			if (!success)
			{
				ans += price;
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

二:

#include<bits/stdc++.h>
using namespace std;
struct ck {
	int v,p,t,b;
};
ck arr[100050],a;
int main() {
 
	long long n,t=0,m=0,sum=0,k;
	cin>>n;
	for(int i=0; i<n; i++) {
		cin>>a.v>>a.p>>a.t;
		if(a.v==0) {
			arr[t].v=a.v;
			arr[t].p=a.p;
			arr[t].t=a.t;
			arr[t].b=0;
			sum+=a.p;
//			cout<<"p:"<<a.p<<" "<<endl;
			t++;
		} else {
			k=-1;
			for(int j=t-1; j>=0; j--) {
				if(a.t-arr[j].t>45) break;
				if(arr[j].p>=a.p&&arr[j].b==0) {
					k=j;
//					cout<<"免单:"<<a.p<<endl;
				}	
			}
			if(k!=-1){
				arr[k].b=1;	
			}
			else {
				sum+=a.p;
			}
		}
	}
//	cout<<endl;
	cout<<sum<<endl;
	return 0;
}
0 0 vote
Article Rating
Subscribe
提醒
3 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments
EricNTH

主题操作记录
2020.5.11 15:10 审核通过

qyh

可以免费帮您扣除,需要联系我

3
0
Would love your thoughts, please comment.x
()
x