首页 > 代码库 > Codeforces Round #422 (Div. 2) C. Hacker, pack your bags! 排序+贪心
Codeforces Round #422 (Div. 2) C. Hacker, pack your bags! 排序+贪心
链接:
http://codeforces.com/contest/822/problem/C
题意:
有x天的假期, 有n张旅行票, 每张票有起始时间l, 结束时间r, 花费cost, 想把假期分成两部分出去旅游, 两部分时间不能重合(ri < lj || rj < li), 问最小花费是多少, 如果不能两部分, 输出-1
题解:
CF官方解法, 效率O(nlogn2)
设置一个结构体, struct P{int p, len, cost, type};
将每张票(l, r, cost)
表示成两个结构体, P(l, r-l+1, cost, -1), P(r, r-l+1, cost, 1);
设置一个数组best[i], 表示时间长度为i的最便宜的票, 一开始全为INF, 之后边用边更新
将结构体数字排序, 首先按p排序, p相同按type排序, 这样保证了是按时间顺序且同样时间type为-1的在type为1的前面
遍历整个结构体数组
type为1, 则用p[i].cost更新best[p[i].len]
type为-1, 则用p[i].cost+best[x-p[i].len]更新ans
因为数组按照p然后type排序, 保证了更新ans是用到的best[], 里面存储的都是根据时间段在之前的票得出的, 保证时间不会重叠
代码:
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 typedef long long ll; 5 const int MAXN = 2E5 + 100, INF = 2e9+10; 6 int n, x, l, r, c; 7 int best[MAXN]; 8 struct P 9 {10 int p, len, cost, type;11 bool operator<(const P &x)12 {13 if(p == x.p) return type < x.type;14 return p < x.p;15 }16 }p[MAXN*2];17 18 19 int main()20 {21 scanf("%d%d", &n, &x);22 int cnt = 0;23 for(int i=0; i<n; ++i)24 {25 scanf("%d%d%d", &l, &r, &c);26 p[cnt++] = P{l, r-l+1, c, -1};27 p[cnt++] = P{r, r-l+1, c, 1};28 }29 ll ans = INF;30 sort(p, p+cnt);31 fill(best, best+x, INF);32 33 for(int i=0; i<cnt; ++i)34 {35 if(p[i].type == -1)36 {37 if(p[i].len < x)38 {39 ans = min(ans, (ll)p[i].cost+(ll)best[x-p[i].len]);40 }41 }42 else best[p[i].len] = min(best[p[i].len], p[i].cost);43 }44 45 if(ans >= INF) ans = -1;46 cout << ans <<endl;47 48 return 0;49 }
Codeforces Round #422 (Div. 2) C. Hacker, pack your bags! 排序+贪心
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。