ギリギリ eye
Description
A.D.1999,由坠落地球的“谜之战舰”带来的 Over Technology,揭示了人类历史和远古文明之间的丝丝联系, 促使人类终止彼此间的战争,一方面面对强大的异星人势力 ,用“文化的力量”寻找生存之道,一方面向着银河系进行移民而寻求新天地。西历 2067 年,银河系边境行星的中心、失去自我而狂暴化的“Bajura”症候群扩大化。眼见事态严重,星间复合企业体为控制症状,以少女们的“战术音乐组合 walküre”与共同作战的“Valkyrie 部队”一起集结。
小风,作为战术音乐组合 walküre 的预备队中的一员,迎来了他的转正试炼!当试炼开始(第 1 个单位时间)时,将会有大量的靶机同时飞起,每一架靶机都有各自的速度和分数(可能相同),其中速度用飞离射击范围的时间来描述。然而,因为试炼用火炮比较老旧,每个单位时间只能射击一发,并不是所有的靶机都能被击落,所以能得到的最高分也不是所有靶机的分数总和。不过由于小风强!无敌他弹无虚发,一炮一个,非常轻松的就拿到了能得到的最高分,现在问题来了,这个最高分是多少呢?PS:配合 BGM: いけないボーダーライン食用此题口感更佳
Input
第一行一个正整数 N, N 最大不超过 1000000
接下来 N 行,每行两个整数 T, V,第 i 行表示第 i-1 号靶将会在 T 时刻后飞出射击范围,击落该靶机能够获得 V 的得分。保证 T 最大不超过 700000.
Output
Sample Input
71 61 73 23 12 42 56 1
Sample Output
15
思路
方法一:为了使得获得的分数最高,那么应该从靶机中时间最长的往前推,这样能保证打尽量多的靶机;推进的过程,当有在当前时刻截止的靶机,则将他们全部放入优先队列里面,然后从中选出获得价值最大的靶机,如果在当前时刻没有截止的靶机,则从优先队列中选出获得最大价值的靶机。
方法二:按照价值从大到小排列,每次选出能获得最大价值的靶机,将其放在截止时刻打击,并做好标记,如果其截止时刻已经有过标记,则从截止时刻往前推,找出一个可以打击的时刻。查找的过程可以用并查集优化。假设一个产品a占用了一个日期后,那么如果下次又有一个产品b和产品a的截止日期是相同的,但是那个日期以被占用了,所以就要往前移动1天,那么就可以用并查集进行标记,在a占用了那个日期后,把a的截止日期指向前一个日期,这样的话,可以直接查找到他要占用到哪一个时间。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn = 1000005; struct Edge { int t,v,nxt; } edge[maxn]; int sz = 0,tot = 0,head[maxn],heap[maxn]; void push(int x) { int i = sz++; while (i > 0) { int p = (i - 1) / 2; if (heap[p] >= x) break; heap[i] = heap[p]; i = p; } heap[i] = x; } int pop() { int ret = heap[0]; int x = heap[--sz]; int i = 0; while (2*i+1 < sz) { int a = i*2 + 1,b = i*2 + 2; if (b < sz && heap[b] > heap[a]) a = b; if (heap[a] <= x) break; heap[i] = heap[a]; i = a; } heap[i] = x; return ret; } void addedge(int t,int v) { edge[tot].v = v,edge[tot].t = t,edge[tot].nxt = head[t]; head[t] = tot++; } int main() { int N,i,j; scanf("%d",&N); int v,t,maxt = 0,res = 0; tot = 0,sz = 0; memset(head,-1,sizeof(head)); memset(heap,0,sizeof(heap)); for (i = 0; i < N; i++) { scanf("%d%d",&t,&v); addedge(t,v); if (t > maxt) maxt = t; } for (i = maxt; i > 0; i--) { if (head[i] != -1) { for (j = head[i]; j != -1; j = edge[j].nxt) { push(edge[j].v); } res += pop(); } else if (sz > 0) { res += pop(); } } printf("%d\n",res); return 0; }
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> using namespace std; const int MAXN = 1000005; int p[MAXN]; struct N { int p, d; bool operator < (const N& t)const { return p > t.p; } }a[MAXN]; int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); } int main() { int n,i; scanf("%d", &n) ; int ans = 0; for (i = 0; i <= MAXN; ++i) p[i] = i; for (i = 0; i < n; ++i) scanf("%d%d", &a[i].d, &a[i].p); sort(a, a + n); for (i = 0; i < n; ++i) { int tmp = find(a[i].d); if (tmp > 0) { p[tmp] = tmp - 1; ans += a[i].p; } } printf("%d\n", ans); return 0; }