2019年Noip普及组复赛第二题解析
本文最后更新于 367 天前,其中的信息可能已经有所发展或是发生改变。

题目如下:

简单说一下我的思路,边输入边比较,地铁就直接把钱存入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原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接: https://nth.ink/cpp/P1930.html

(广告由我们的赞助商提供,内容与本站无关)

评论

  1. Tianheng Ni
    Tianheng Ni 博主
    Windows Chrome 81.0.4044.138
    1年前
    2020-5-11 15:10:43

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

    • Xuheng Zhang
      Xuheng Zhang
      Windows Firefox 75.0
      1年前
      2020-5-11 16:59:30

      nth,那个EB换实物什么时候搞好啊?我1000多EB放着没用。。。

      • Yihao Qin
        Yihao Qin 博主
        Windows Chrome 84.0.4142.0
        1年前
        2020-5-11 18:15:34

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

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇