列表

详情


NC233152. 超市

描述

    小沙的好朋友开了一家超市,小沙为了去支持他的朋友,所以小沙想去他那买东西,持续若干天,但是小沙非常的贫穷,他只能买最便宜的商品来支持朋友。
    朋友的店里有若干种衣服,每种衣服在一段时间内会有折扣,所以小沙想请教你,对于每一天来说,当天最便宜的衣服是哪一件,如果有多件,那么输出编号靠前的一位。
    对于打折的方式为 ,其中x为原价,y为折扣。
    其中注意对于折扣区分为两种:
    若原价为100,折扣为9折,那么折后价为
    若原价为100,折扣为85折,那么折后价为
    题目保证输入不会出现小于1折的折扣。

输入描述

第一行输入三个数字 分别代表朋友店中的衣服数目,小沙要去购物的天数,折扣数目。
第二行 输入个数字 分别代表衣服的原价
第3~q+2行,每行四个数字x,y,l,r分别代表 打折衣服的标号,打折,持续的天数区间(范围为闭区间也就是)
题目保证对于每一个物品,他的折扣期间不相交。
对于所有数据均有
对于50%的数据:
对于100%的数据:

输出描述

输出一行
一行包含m个整数,每个整数之间用空格间隔。

示例1

输入:

10 10 4
163 193 149 124 176 127 101 125 153 100
7 4 4 6
4 86 1 5
3 44 4 5
1 27 1 7

输出:

1 1 1 7 7 7 1 10 10 10

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 70ms, 内存消耗: 7712K, 提交时间: 2022-02-14 20:52:19

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
struct node
{
	int val,id,r;
	bool operator <(const node &t)const
	{
		return val==t.val?id>t.id:val>t.val;
	}
};

struct st{int val,id,r;};
priority_queue<node>q;
int a[N];
vector<st>g[N];
int main()
{
	int n,m,t;
	scanf("%d%d%d",&n,&m,&t);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)q.push({a[i],i,m});
	
	for(int i=1;i<=t;i++)
	{
		int x,y,l,r;
		scanf("%d%d%d%d",&x,&y,&l,&r);
		if(y<10)y*=10;
		g[l].push_back({a[x]*y/100,x,r});
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<g[i].size();j++)
		{
			st k=g[i][j];
			q.push({k.val,k.id,k.r});
		}
		while(q.top().r<i)q.pop();
		printf("%d ",q.top().id);
	}
	return 0;
}

上一题