Codeforces Global Round B Tape
题目：点我转移
【题意】
x轴上有m个连续的点,从1标号到m.
其中有n个点是特殊点。
让你用k段区间将这n个点覆盖。
要求区间的总长度最小。
解：
一开始假设我们需要n个胶带(即包含每一个点)
然后因为m<=n
所以可能胶带不够用。
那么就得一个胶带跨过两个点。
怎么选择最好呢?
可以把b[i]-b[i-1]-1处理出来排个序。
(优先取较小的花费)
然后取前n-m个累加和sum。
因为每取一个就少用一段胶带.
AC代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+10; int a[maxn]; int b[maxn]; int main() { int n,k,m; cin>>n>>k>>m; for(int i=0;i<n;i++) cin>>a[i]; int p=0; for(int i=1;i<n;i++) b[p++]=a[i]-a[i-1]-1; ll ans=0; ans+=n; sort(b,b+p); for(int i=0;i<n-m;i++) ans+=b[i]; cout<<ans<<endl; return 0; }
查看9道真题和解析