NC233152. 超市
描述
输入描述
第一行输入三个数字 分别代表朋友店中的衣服数目,小沙要去购物的天数,折扣数目。第二行 输入个数字 分别代表衣服的原价第3~q+2行,每行四个数字分别代表 打折衣服的标号,打折,持续的天数区间(范围为闭区间也就是)题目保证对于每一个物品,他的折扣期间不相交。对于所有数据均有对于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; }