————directory————

—>>TOPIC

—>>IDEAS

—>>CORRECT CODE

—>>CONCLUSION

1.题目

由于长期没有得到维修，A国的高速公路上出现了 n 个坑。为了尽快填补好这 n 个坑，A国决定对 m 处地段采取交通管制。为了求解方便，假设A国的高速公路只有一条，而且是笔直的。现在给出 n 个坑的位置，请你计算，最少要对多远的路段实施交通管制？

2.思路

输入的N可以表示为有N个点，其实也可以表示为N-1条线段。 输入的M，表示留下M条线段，也可以表示为去掉（N- 1）- M + 1及N-M条线段。 为了让留下的线段最少则要让去掉的线段最长，所以要sort排序，再删掉最大的M条线段。

3.AC代码

#include <bits/stdc++.h>
using namespace std;
int n,m,t,ans = 0;
int a[20010],b[20010];
int main()
{
    cin >> n >> m >>a[0];
    for (int i = 1;i < n;i++)
    {
        cin >> a[i];
        b[i - 1] = a[i] - a[i - 1];
    }
    sort(b,b + n);
    for (int i = 0;i < n - m + 1;i++)
    {
        ans += b[i];
    }
    cout << ans + m;
    return 0;
}

4.结束语

此题比较简单😄

编码不易😕

只需点个赞！❤️ ❤️ ❤️

相邻两个管制路段之间，会有一段没有被管制的路。有m个管制路段，因此有m-1个段没有被管制的路。n个坑之间有n-1段路，找出这些路里面最长的m-1个，作为没有被管制的路，求出剩下的n-m段路的总长度即可。由于题目所求的长度是包含两个端点的，因此每一段管制路段都少算了1，最终结果加m即可。

for (int i = 1; i < n; i++)
{
    cin >> a[i];
    b[i - 1] = a[i] - a[i - 1];
}
sort(b, b + n);
for (int i = 0; i < n - m + 1; i++)
    ans += b[i];
cout << ans + m;

还可以优化吗？ 但也AC了 😂

#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long w[15005],q[15005],s,e;
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>q[i];
    }
    s=q[1];
    e=q[n];
    for(int i=1;i<=n-1;i++)
    {
        w[i]=q[i+1]-q[i]-1;
    }
    sort(w+1,w+n,cmp);
    int ans=e-s+1;
    for(int i=1;i<m;i++)
    {
        ans-=w[i];
    }
    cout<<ans;
    return 0;
}

看到大家都是用两个数组解题，我便想了一个只用一个数组解题的方法，数组a代表相邻两坑洞的差，这些差的和先设置为ans,但这个只算了一头，所以需加一，而减去最大m-1个差时，由于两端仍需封闭，而差值只算了一边，所以需要加m-1，综上只需对ans加上m-1+1即m,再去减去m-1个最大差值即可 得满分

#include <bits/stdc++.h>
using namespace std;
int a[15005];
int main()
{
	int n,m;
	cin >> n >> m;
	long int x,ans = 0;
	cin >> x;
	long int q;
	for (int i = 2;i <= n;i++)
	{
		q = x;
		cin >> x;
		a[i] = x - q;
		ans += a[i];
	}
	sort(a,a+n+1);
	for (int i = n;i >= n - m + 2;i--)
	{
		ans -= a[i];
	}
	ans += m;
	cout << ans;
	return 0;
}//已AC，请谨慎使用，勿忘点赞！！！

#include<bits/stdc++.h>
using namespace std;
int n,m;
//LONGLONG太大材小用了
int w[15005],q[15005],s,e;
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>q[i];
    }
    s=q[1];//起始端
    e=q[n];//结束端
    //算间距要去掉两头（植树问题两头不栽）
    for(int i=1;i<=n-1;i++)
    {
        w[i]=q[i+1]-q[i]-1;
    }
    sort(w+1,w+n,cmp);
    int ans=e-s+1;
    //取其中“坑间距”最长的分段分出（m-1）个口
    for(int i=1;i<m;i++)
    {
        ans-=w[i];
    }
    cout<<ans;
    return 0;
}