cf822C(贪心)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接: http://codeforces.com/problemset/problem/822/C

题意: 有n条线段(n<=2e5) 每条线段有左端点li，右端点ri，价值cost（1 <= li <= ri <= 2e5, cost <= 1e9)；

对于一个给定的x(x <= 2e5)，寻找两个不相交的线段，使它们的长度和恰好为x，并且价值和最小；

思路: xjb贪心

这题目肯定是枚举一条线段再找剩下一条线段, 假设枚举右线段, 且其长为len1, 那么我们需要找这条线段左边的长度为 x - len1 的线段的 cost 最小值；直接暴力的话是n^2的复杂度, 肯定 tle. 可以给这些线段按照左右端点排下序, 那么我们可以从按左端点排序的数组中枚举右线段, 然后在按右端点排序的数组中找左线段；但是如果暴力找的话时间复杂度还是 n^2 . 我们可以维护一个 vis数组, vis[i] 为当前右线段的左边线段中长度为 i 的 cost 最小值, 那么 vis[x - len1] 即为当前左线段的 cost 最小值；

那么 cost1 + vis[x - len1] 的最小值即为答案啦；

代码:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define ll long long
using namespace std; const int MAXN = 2e5 + ;
const int inf = 0x7f7f7f7f;
ll vis[MAXN];
struct node{
int l, r;
ll w;
}gel1[MAXN], gel2[MAXN]; bool cmp1(node a, node b){
return a.l < b.l;
} bool cmp2(node a, node b){
return a.r < b.r;
} int main(void){
int n, x;
ll ans = inf;
scanf("%d%d", &n, &x);
for(int i = ; i < n; i++){
scanf("%d%d%lld", &gel1[i].l, &gel1[i].r, &gel1[i].w);
gel2[i] = gel1[i];
}
sort(gel1, gel1 + n, cmp1);
sort(gel2, gel2 + n, cmp2);
memset(vis, 0x7f, sizeof(vis));
int indx = ;
for(int i = ; i < n; i++){
ll gg = gel1[i].w;
while(indx < n && gel2[indx].r < gel1[i].l){
int cnt = gel2[indx].r - gel2[indx].l + ;
if(vis[cnt] > gel2[indx].w) vis[cnt] = gel2[indx].w;
indx++;
}
int cc = x - (gel1[i].r - gel1[i].l + );
if(cc <= ) continue;
gg += vis[cc];
if(ans > gg) ans = gg;
}
if(ans == inf) cout << - << endl;
else cout << ans << endl;
return ;
}