codeforce每日一题链接
题目链接
题目分数:1900
题目描述
给你$n$个数对,保证$l[i]<=r[i]<l[i+1]-1$,你从$0$开始,有三种操作,第一种是想向右移动$1$,第二种是按下上色的按钮,第三种是松开上色的按钮。注意,你只能在$l[i]$到$r[i]$的范围内上色。请问怎样用最少的操作给$k$个位置上色。
样例
输入样例1
4
2 3
1 3
1 4
4 20
10 13 16 19
11 14 17 20
2 3
1 3
1 10
2 4
99 999999999
100 1000000000
输出样例1
8
-1
7
1000000004
算法
(贪心) $O(n)$
这道题重点在于长度为1的区间能不能直接选,答案是不能直接选,因为选了之后可能会亏了。这个在样例1的第3组就可以看出来。因为要上色就一定要操作两次,而为区间长度为1不如为下一个较长的区间上色,当然前提是我们要能选到下一个区间。那代码怎么写呢,我们可以动态维护长度为1的区间有多少个,比较长度大于等于2的区间总和和m的大小,维护最小值。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
inline void solve()
{
cin>>n>>m;
vector<PII> w(n);
rep(i, 0, n-1) cin>>w[i].fi;
rep(i, 0, n-1) cin>>w[i].se;
int k = 0, cnt = 0;
LL res = 3e9;
rep(i, 0, n-1)
{
if(w[i].se-w[i].fi+1>1) k += w[i].se - w[i].fi + 1;
else cnt ++;
if(k < m){
if(k + cnt >= m)
{
res = min(res, (LL)w[i].se + 2 * (i - cnt + 1 + m - k));
}
}else{
res = min(res, (LL)w[i].se + m - k + 2 * (i - cnt + 1));
break;
}
}
if(res == 3e9) res = -1;
cout<<res<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}