pku 1456 Supermarket

深碍√TFBOYSˉ_ 2022-07-12 10:10 164阅读 0赞

\#include <iostream> \#include <cstdio> \#include <algorithm> using namespace std; \#define N 10005 struct Product \{ int profit; int deadline; bool operator < (const Product& rhs) const \{ return deadline < rhs.deadline; \} \}; int profit\[N\]; Product product\[N\]; int main() \{ int n; int i, j; while(scanf("%d", &n) != EOF) \{ int maxDeadline = -1; memset(profit, 0, sizeof(profit)); for(i = 0; i < n; ++i) \{ scanf("%d%d", &product\[i\].profit, &product\[i\].deadline); if(product\[i\].deadline > maxDeadline) maxDeadline = product\[i\].deadline; \} sort(product, product+n); for (i = 0; i < n; ++i) \{ if(profit\[product\[i\].deadline\] == 0) profit\[product\[i\].deadline\] = product\[i\].profit; else \{ int value = product\[i\].profit; int minValue = INT\_MAX; int minIndex = -1; for(j = 1; j <= product\[i\].deadline; ++j) \{ if(profit\[j\] == 0) \{ profit\[j\] = value; break; \} if(profit\[j\] < minValue) \{ minValue = profit\[j\]; minIndex = j; \} \} if(j > product\[i\].deadline && value > profit\[minIndex\]) profit\[minIndex\] = value; \} \} int sum = 0; for(i = 1; i <= maxDeadline; ++i) sum += profit\[i\]; printf("%d/n", sum); \} return 0; \}

本题还可以用小顶堆优化, 将时间复杂度降到O(N\*logN).

发表评论取消回复

表情：

评论列表（有 0 条评论，164人围观）

还没有评论，来说两句吧...

相关阅读

相关【左偏树】[LuoguP1456] Monkey King

多...多组数据... awsl 死命的MLE，原来是忘记清空数组了.... 左偏树模板？对于每一个操作，我们把两个节点$x,y$的祖先$fx,fy$找到，然后把他们

客官°小女子只卖身不卖艺/ 2023年06月01日 06:08/ 0 赞/ 15 阅读

相关 chef supermarket入门

下载安装模块 knife supermarket install grafana 9.5.1 创建和编写测试模块 cd cookbooks mkd

今天药忘吃喽~/ 2022年12月25日 05:00/ 0 赞/ 140 阅读

相关【贪心+并查集优化】Supermarket

A supermarket has a set Prod of products on sale. It earns a profit px for each product

客官°小女子只卖身不卖艺/ 2022年11月14日 00:45/ 0 赞/ 134 阅读

相关 pku 3176 水

\include <iostream> \include <cstdio> \include <cstring> using namespace std; int map\[3

我不是女神ヾ/ 2022年08月14日 04:46/ 0 赞/ 168 阅读

相关 pku 1088 滑雪

\include <iostream> using namespace std; int map\[100\]\[100\]; int v\[100\]\[100\]; int

╰半夏微凉°/ 2022年08月13日 12:46/ 0 赞/ 191 阅读

相关 pku 1456 Supermarket

\include <iostream> \include <cstdio> \include <algorithm> using namespace std; \define

深碍√TFBOYSˉ_/ 2022年07月12日 10:10/ 0 赞/ 165 阅读

相关 pku 3176

\include<stdio.h> int str\[351\]\[351\]; int main() \{ int n,i,j; // freopen("

小鱼儿/ 2022年06月17日 23:29/ 0 赞/ 151 阅读

相关贪心的一道题 Supermarket

POJ 1456 描述 A supermarket has a set Prod of products on sale. It earns a profit px for

痛定思痛。/ 2022年06月13日 09:19/ 0 赞/ 165 阅读

相关 POJ 1456 Supermarket（贪心）

A supermarket has a set Prod of products on sale. It earns a profit px for each product

妖狐艹你老母/ 2022年06月09日 02:07/ 0 赞/ 169 阅读

相关 poj-1456

<table style="font-family:"Microsoft YaHei""> <tbody> <tr> <td>

Myth丶恋晨/ 2022年06月01日 08:28/ 0 赞/ 133 阅读