首页 > 代码库 > 1163 最高的奖励 贪心 + 并查集
1163 最高的奖励 贪心 + 并查集
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1163
首先如果时间大于n,也就是相当于不限时了,因为完成前n - 1项任务需要时间n - 1,不影响我的第n项。
首先按价值排序,然后这个价值安排在它准备过期的那一天,如果被占据了,就找下一天,就能优先吃到了最大值。而且你吃其他也是耗费一个空间,所以吃个更大的是最优的。
然后可以用并查集来维护,记录topre[i]表示第i个位置的上一个空位是谁。
就能加速找到了。
不然有数据卡的,就是全部都是49999 然后权值是1--50000
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> const int maxn = 50000 + 20; struct node { int tim, val; int id; bool operator < (const struct node & rhs) const { return val < rhs.val; } }a[maxn]; int topre[maxn]; bool pos; int tofind(int t) { if (t == 0) return 0; if (topre[t] == t) { topre[t] = t - 1; pos = true; return t - 1; } topre[t] = tofind(topre[t]); } void work() { int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d%d", &a[i].tim, &a[i].val); } sort(a + 1, a + 1 + n); for (int i = 1; i <= n; ++i) topre[i] = i; LL ans = 0; for (int i = n; i >= 1; --i) { if (a[i].tim >= n) { ans += a[i].val; continue; } pos = false; tofind(a[i].tim); // cout << pos << endl; if (pos != false) ans += a[i].val; } cout << ans << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
1163 最高的奖励 贪心 + 并查集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。