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

本文作者：Zhang, Xuheng  本文分类：编程学习笔记  浏览：928
阅读时间：1111字, 约1-2分钟

题目如下：

简单说一下我的思路，边输入边比较，地铁就直接把钱存入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;
}

关于作者Zhang, Xuheng

• 还没有填写个人简介
• Email: hy23682@126.com
• 注册于: 2020-04-07 05:11:14