青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

oyjpArt ACM/ICPC算法程序設(shè)計(jì)空間

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

Supermarket
Time Limit:2000MS  Memory Limit:65536K
Total Submit:987 Accepted:369

Description
A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral number of time units starting from the moment the sale begins. Each product takes precisely one unit of time for being sold. A selling schedule is an ordered subset of products Sell ≤ Prod such that the selling of each product x∈Sell, according to the ordering of Sell, completes before the deadline dx or just when dx expires. The profit of the selling schedule is Profit(Sell)=Σx∈Sellpx. An optimal selling schedule is a schedule with a maximum profit.
For example, consider the products Prod={a,b,c,d} with (pa,da)=(50,2), (pb,db)=(10,1), (pc,dc)=(20,2), and (pd,dd)=(30,1). The possible selling schedules are listed in table 1. For instance, the schedule Sell={d,a} shows that the selling of product d starts at time 0 and ends at time 1, while the selling of product a starts at time 1 and ends at time 2. Each of these products is sold by its deadline. Sell is the optimal schedule and its profit is 80.


Write a program that reads sets of products from an input text file and computes the profit of an optimal selling schedule for each set of products.

 

 

 

 

 

Input
A set of products starts with an integer 0 <= n <= 10000, which is the number of products in the set, and continues with n pairs pi di of integers, 1 <= pi <= 10000 and 1 <= di <= 10000, that designate the profit and the selling deadline of the i-th product. White spaces can occur freely in input. Input data terminate with an end of file and are guaranteed correct.

Output
For each set of products, the program prints on the standard output the profit of an optimal selling schedule for the set. Each result is printed from the beginning of a separate line.

Sample Input

4  50 2  10 1   20 2   30 1
7  20 1   2 1   10 3  100 2   8 2
5 20  50 10

 

 

 

 

 

Sample Output

80
185

 

 

 

 

 

Hint
The sample input contains two product sets. The first set encodes the products from table 1. The second set is for 7 products. The profit of an optimal schedule for these products is 185.

Source
Southeastern Europe 2003


貪心是很容易想到的 盡可能將利潤(rùn)大的選中 然后盡可能放到DeadLine附近去

這里就有一個(gè)問(wèn)題 怎樣盡快拿到一個(gè)deadLine往上數(shù)第一個(gè)空閑日期?

想法0:直接搜o(n^2)的查找總費(fèi)時(shí) 可能超時(shí)!

想法1:線段樹!問(wèn)題建模:一個(gè)數(shù)的前面第幾個(gè)是空閑?
對(duì)10000的區(qū)間建立線段樹 可以將查詢復(fù)雜度降低到NlogN

想法2:   并查集!對(duì)一個(gè)連續(xù)非空閑區(qū)間建立集合 其代表元選擇上面第一個(gè)空閑的日期!時(shí)間復(fù)雜度再降低到o(N)! 系數(shù)為ackman函數(shù) 很小

Problem Id:1456  User Id:oyjpart
Memory:172K  Time:15MS
Language:G++  Result:Accepted

//by oyjpArt
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 10010;
int ng;
struct good{int p, d;}g[N];
int p[N];
bool flag[N];

bool operator < (const good& a, const good& b) {return a.p > b.p; }

int find_set(int a) {
 int t = a;
 while(t != p[t]) t = p[t];
 int r = a;
 while(r != p[r]) { int k = p[r]; p[r] = t; r = k; }
 return t;
}

int main() {
 int i;
 while(scanf("%d", &ng) != EOF) {
  memset(flag, 0, sizeof(flag));
  int maxd = 0;
  for(i = 0; i<ng; i++) {
   scanf("%d%d", &(g[i].p), &(g[i].d));
   if(g[i].d > maxd) maxd = g[i].d;
  }
  for(i = 1; i<maxd; i++)
   p[i] = i;
  sort(g, g+ng);
  int cnt = 0;
  for(i = 0; i<ng; i++) {
   int d;
   if(!flag[g[i].d]) { d = g[i].d; p[d] = d-1; }
   else d = find_set(g[i].d);
   if(d > 0) cnt += g[i].p;
   flag[d] = 1;
   if(d > 0 && flag[d+1]) p[d] = p[d-1];
  }
  printf("%d\n", cnt);
 }
 return 0;
}

Feedback

# re: PKU 1456 Supermarket 并查集加速實(shí)例  回復(fù)  更多評(píng)論   

2007-03-11 18:39 by nick
if(flag[d+1]) p[d] = p[d-1];

加這一行的目的在哪呢?

# re: PKU 1456 Supermarket 并查集加速實(shí)例  回復(fù)  更多評(píng)論   

2007-03-11 20:07 by oyjpart
p[d]代表選中在D之前第一個(gè)空閑的日子
就是說(shuō)d這個(gè)日期用了之后 那么第一個(gè)空閑的日子就一定時(shí)p[d-1];
也可以這樣寫:
for(i = 0; i<ng; i++) {
int d = g[i].d;
if(flag[g[i].d]) d = find_set(g[i].d);
if(d > 0) cnt += g[i].p;
flag[d] = 1;
p[d] = p[d-1]; //如果p[d-1]沒用用過(guò) 那么p[d-1]就應(yīng)該=d-1
}

# re: PKU 1456 Supermarket 并查集加速實(shí)例  回復(fù)  更多評(píng)論   

2007-03-12 03:00 by nick
@oyjpart

可以舉個(gè)例子嗎? 真的有些難懂
什麼情況會(huì)需要用到這個(gè)
抱歉, 謝謝你的回覆

# re: PKU 1456 Supermarket 并查集加速實(shí)例  回復(fù)  更多評(píng)論   

2007-03-12 17:20 by oyjpart
抱歉 我說(shuō)的不是很清楚

首先 我這里的p[]數(shù)組代表的時(shí)parent 也就是在樹形的并查集中父結(jié)點(diǎn)的標(biāo)號(hào) 比如 如果1節(jié)點(diǎn)(根)的子節(jié)點(diǎn)是2,3 則p[2] = p[3] = 1; 而根節(jié)點(diǎn)的父結(jié)點(diǎn)將會(huì)被初始化為自己的標(biāo)號(hào) 如p[1] = 1;
在樹形的并查集中 我們將根節(jié)點(diǎn)定義為這個(gè)集合的代表元
而在這個(gè)題目中我們將代表元定義為這個(gè)從某一天往上數(shù)第一個(gè)空閑的日期 比如 日期
1 2 3 4 5 6 7 8 9 10
如果3是空閑(沒有被分配一個(gè)商品)而4,5都已經(jīng)分配 那么p[4]=p[5] = 3;
如果4也是空閑 那么p[3] = 3; p[4] = 4;
這樣 我們?cè)诜峙渖唐返臅r(shí)候 要得到從某一天往上數(shù)第一個(gè)空閑的日期 就是直接查找這一天所在集合里面的代表元就可以了
從另外一個(gè)角度上來(lái)看 這個(gè)集合其實(shí)時(shí)一個(gè)空閑的天 后面跟著一連串的非空閑天
比如
1 2 3 4 5 6 7 8 9 10
如果3是空閑(沒有被分配一個(gè)商品)而4,5都已經(jīng)分配 6沒有分配 那這個(gè)集合就是3,4,5 其中代表元為3
以下面這段代碼來(lái)作說(shuō)明吧
for(i = 0; i<ng; i++) {
int d = g[i].d;
if(flag[g[i].d]) d = find_set(g[i].d);
if(d > 0) cnt += g[i].p;
flag[d] = 1;
p[d] = p[d-1]; //如果p[d-1]沒用用過(guò) 那么p[d-1]就應(yīng)該=d-1
}
如果flag[g[i].d] is true 代表g[i].d這一天已經(jīng)被分配 于是空閑的天就是find_set(g[i].d);
否則 d = g[i].d; 就是這一天 這個(gè)時(shí)候集合只有一個(gè)元素 就是自己作為代表元
if(d > 0) cnt += g[i].p; 因?yàn)橛锌赡艽碓獮?(設(shè)置數(shù)據(jù)的時(shí)候p[d-1]為了不越界 故意留出0) 實(shí)際上代表沒有空閑 比如1,2,3,4都滿了 你要放在3的地方 就會(huì)得到0 這個(gè)位置 所以要>0才能cnt += g[i].p;
flag[d] = 1; 接著把剛才找到的空閑處標(biāo)記
p[d] = p[d-1]; 然后把剛才找到的空閑處的代表元設(shè)置一下
這里的設(shè)置對(duì)于下面2中情況都是對(duì)的
情況1: 1 2 3 4 5
2空閑 3空閑 我在3處放 然后標(biāo)記p[3] = p[2] = 2;
情況2: 1 2 3 4 5 6
2滿 3滿 4空閑 我在4處放 然后標(biāo)記 p[4] = p[3] = 1
基本上就是這樣了 沒有解釋清楚 真不好意思 :)

# re: PKU 1456 Supermarket 并查集加速實(shí)例  回復(fù)  更多評(píng)論   

2007-03-18 21:51 by nick
呵呵, 真的很謝謝你回覆這麼說(shuō)
我懂
for(i = 0; i<ng; i++) {
int d = g[i].d;
if(flag[g[i].d]) d = find_set(g[i].d);
if(d > 0) cnt += g[i].p;
flag[d] = 1;
p[d] = p[d-1]; //如果p[d-1]沒用用過(guò) 那么p[d-1]就應(yīng)該=d-1
}

但就是不懂原本程序的 if(flag[d+1]) p[d] = p[d-1]; 這一行的意義在哪

如果這個(gè)程序不加這一行是一定會(huì)錯(cuò)

但什麼樣的 case 會(huì)導(dǎo)致錯(cuò)誤呢?

# re: PKU 1456 Supermarket 并查集加速實(shí)例  回復(fù)  更多評(píng)論   

2007-03-18 21:56 by nick
喔喔, 我想到了.. 呵呵, 謝謝你

原本那樣寫讓我比較不好理解

不過(guò)後來(lái)的寫法
p[d] = p[d-1]; //如果p[d-1]沒用用過(guò) 那么p[d-1]就應(yīng)該=d-1

這邊要 if(d>0) 不然 p[d-1] 會(huì) runtime error ^^

# re: PKU 1456 Supermarket 并查集加速實(shí)例  回復(fù)  更多評(píng)論   

2007-03-19 17:37 by oyjpart
o 對(duì) 呵呵~~ 我改一下
:)
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲一区欧美| 一色屋精品亚洲香蕉网站| 亚洲老板91色精品久久| 亚洲国产高清一区| 欧美国产综合| 亚洲特级片在线| 欧美一级大片在线免费观看| 一区二区三区在线视频免费观看 | 国产一区二区欧美| 久久久久久国产精品mv| 久久精品人人爽| 亚洲欧洲综合| 日韩亚洲欧美一区二区三区| 国产乱码精品一区二区三区忘忧草| 久久成人精品| 久久这里有精品15一区二区三区| 亚洲人成欧美中文字幕| 一本色道久久综合亚洲精品高清 | 国产午夜精品视频免费不卡69堂| 久久精品视频在线看| 欧美大胆人体视频| 亚洲欧美区自拍先锋| 久久久久国内| 亚洲天堂av在线免费| 久久久久久久久久久成人| 99视频精品在线| 欧美一级久久| 一区二区三区日韩精品视频| 999亚洲国产精| 亚洲欧美日韩成人| 亚洲精品美女久久7777777| 亚洲午夜精品久久| 亚洲日本精品国产第一区| 亚洲一区二区视频在线观看| 亚洲日本理论电影| 欧美资源在线观看| 亚洲欧美精品中文字幕在线| 免费观看在线综合| 久久中文字幕一区二区三区| 国产精品av免费在线观看| 欧美高清在线一区二区| 国产午夜精品视频| 亚洲一级黄色av| 日韩视频中午一区| 老牛影视一区二区三区| 久久国产直播| 国产精品揄拍500视频| 亚洲激情成人网| 亚洲电影第三页| 久久精品夜色噜噜亚洲aⅴ| 亚洲欧美日韩精品在线| 欧美日韩国产区一| 亚洲人成网站999久久久综合| 精品盗摄一区二区三区| 欧美一区二区三区精品| 久久av二区| 国产精品私人影院| 亚洲图片欧美一区| 亚洲免费中文字幕| 欧美吻胸吃奶大尺度电影| 亚洲美女视频在线观看| 中文一区二区在线观看| 欧美连裤袜在线视频| 亚洲激情视频网站| 夜夜爽99久久国产综合精品女不卡 | 亚洲性感美女99在线| 欧美国产先锋| 亚洲激情综合| 亚洲欧洲日韩女同| 欧美丰满高潮xxxx喷水动漫| 欧美福利视频网站| 亚洲精品视频在线看| 欧美成人激情视频免费观看| 亚洲第一区在线观看| 亚洲人成网站777色婷婷| 欧美激情一二区| 亚洲精品美女免费| 亚洲综合成人婷婷小说| 国产精品丝袜xxxxxxx| 亚洲欧美久久久| 久久日韩粉嫩一区二区三区| 激情一区二区三区| 欧美大片在线观看| 一本综合精品| 久久精品二区亚洲w码| 在线看日韩av| 欧美精品日韩| 亚洲影院免费| 久久一区二区三区四区| 亚洲精品久久在线| 国产精品扒开腿做爽爽爽视频 | 亚洲一区在线免费| 久久激情久久| 亚洲精品一区二区三| 欧美日韩综合一区| 一本色道久久| 国产精品青草综合久久久久99 | 香蕉久久久久久久av网站| 久久综合999| 一区二区三区日韩精品| 国产三级精品三级| 欧美激情女人20p| 亚洲欧洲99久久| 亚洲国产另类久久久精品极度| 亚洲香蕉网站| 亚洲高清在线播放| 欧美性久久久| 麻豆免费精品视频| 午夜视频在线观看一区二区| 欧美激情片在线观看| 性欧美激情精品| 亚洲欧洲日本一区二区三区| 国产酒店精品激情| 欧美人体xx| 久久久久久亚洲综合影院红桃| aa成人免费视频| 欧美不卡一区| 久久久免费精品视频| 在线一区二区三区四区| 亚洲高清免费在线| 国产一区二区三区久久久久久久久| 欧美—级高清免费播放| 久久噜噜噜精品国产亚洲综合| 国产精品99久久久久久久vr| 亚洲第一精品夜夜躁人人躁 | 亚洲第一二三四五区| 国产精品尤物| 国产精品狼人久久影院观看方式| 欧美激情一区二区三区四区| 久久免费99精品久久久久久| 午夜一区在线| 亚洲一区二区三区在线看| 亚洲精品中文字| 欧美激情在线有限公司| 蜜臀av性久久久久蜜臀aⅴ四虎| 欧美一区二区三区免费在线看| 国产精品99久久99久久久二8| 亚洲久色影视| 亚洲精品网站在线播放gif| 亚洲黄网站在线观看| 影音先锋另类| 伊人久久婷婷| 亚洲高清在线观看| 91久久精品视频| 亚洲精华国产欧美| 91久久精品一区| 亚洲精品中文字幕有码专区| 最近中文字幕mv在线一区二区三区四区 | 欧美精品久久一区二区| 蜜臀久久99精品久久久久久9| 久久综合中文| 欧美超级免费视 在线| 欧美黄色片免费观看| 欧美日韩美女一区二区| 欧美日韩性生活视频| 欧美性淫爽ww久久久久无| 国产精品草草| 国产亚洲欧洲997久久综合| 国产网站欧美日韩免费精品在线观看| 国产精品久久久久久久久久免费看 | 欧美aaa级| 亚洲三级电影全部在线观看高清| 日韩视频一区| 亚洲一区二区三区777| 久久大逼视频| 欧美成人精品一区二区三区| 欧美日韩国产成人在线91| 国产精品美女久久久久久免费| 国产在线一区二区三区四区| 亚洲福利国产精品| 亚洲一二三区精品| 久久亚洲高清| 亚洲精品九九| 欧美在线免费视频| 欧美mv日韩mv国产网站app| 欧美三级乱码| 在线免费观看视频一区| 亚洲午夜久久久久久久久电影网| 久久精品一区二区国产| 91久久国产综合久久| 性色av一区二区三区在线观看| 蜜桃av一区二区三区| 国产精品羞羞答答| 99热在线精品观看| 久久久夜夜夜| 99riav1国产精品视频| 久久蜜桃资源一区二区老牛| 欧美无乱码久久久免费午夜一区| 狠狠色丁香久久婷婷综合丁香| 在线亚洲欧美视频| 欧美国产高潮xxxx1819| 亚洲欧美综合精品久久成人| 欧美人交a欧美精品| 在线成人激情黄色| 久久成人这里只有精品| 日韩一二三区视频| 母乳一区在线观看| 影音先锋另类| 久久网站免费| 午夜精品久久久久久久久|