题目链接：P11639 Line Game。

个人见解：

这道题的难度我估摸着有

50\%

来自题面理解。毕竟这道题无论是从代码还是思维来讲都不像绿的难度。当然只是个人意见，不作参考。

进入正题：

既然题目难理解，那就先从题目下手。

题目大意：

在一个长度为

m+1

的坐标轴上，你从坐标

1

开始，要进行多次操作。

操作内容是给出一些元素，你要删除他们。

删除有两种情况，分别为全部删除或部分删除。

删除元素遵循以下操作：

选定一个值域 $[L,R]$ ，在这个值域内的所有元素被删除，并付出相应代价，大小为 $R-L+1$ 。
若没有全部删除，则你的坐标 $+1$ ，你要在到达 $m+2$ （即出界）之前删除所有元素。

最后输出最小代价和。

题目简化：

多次给出一些元素，全部删除或部分删除，删除付出被删除元素的极差的代价，只能进行 $m$ 次部分删除。求出删除所有元素的最小代价和。

题目分析：

题目中要求代价和最小，那么我们要尽可能的使代价被充分利用。因为代价与值域有关，而值域又与元素分布有关，我们要让元素分布集中，最好的方法就是将不集中的元素分成多个集中的部分，也就是部分删除。

因为部分删除只能使用

m

次，所以要尽可能减少不被利用的值域的长度。那我们可以用一个数组

e

来记录下给出的元素，排序后二次处理求差,再开一个

res

数组记录下来，这个过程就是计算出所有不被利用的值域。用 vector 记录方便又适合，是不二之选。

CPP

	vector<int> e;//记录每一条线段的元素 
	vector<int> res;//记录每条线段上相邻元素的差值

计算答案可以使用整体减空白思想。即用每一组元素的极差之和（代码中最开始记为

ans

），减去被去除的值域的长度，最后得到答案。

代价和最小

\iff

去除的值域长度最大

。

这是显而易见的，为了达到这一目的，我们要对

res

数组进行降序排序，将前

m

个(或者不达

m

个，选择全部差值)，全部删除。用代码写就是：

CPP

	For(i,0,res.size()-1){
		if(i>=m-1||res[i]<=0) break;
		ans-=res[i]; 
	}

注意事项：

在计算极差和值域长度时存在是否

+1

的常规细节，读者要仔细斟酌。

Code呈现：

CPP

#include<bits/stdc++.h>
//万能头YYDS 
using namespace std;
namespace LKSN{
    template <typename T>
    inline void read(T &x){
       x=0; T f=1;char ch;
       while(!isdigit(ch=getchar())) f-=(ch=='-')<<1;
       while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
       x*=f;
    }
    template <typename T, typename ...L>
    inline void read(T &x,L &...y){
        read(x);
        read(y...);
    }
    template <typename T>
    inline void write(T x){
        if(x<0) putchar('-'),x=-x;
        if(x>9) write(x/10);
        putchar(x%10+'0');
    }
    template <typename T, typename ...L>
    inline void write(T &x,L &...y){
        write(x),putchar(' ');
        write(y...);
    }
}//快读快写 
using namespace LKSN; 
#define ll long long
#define rint register int
#define For(i,a,b) for(rint i=a;i<=b;i++)
#define foR(i,a,b) for(rint i=a;i>=b;i--)
#define FOr(i,a,b,c) for(rint i=a;i<=b;i+=c)
#define fOR(i,a,b,c) for(rint i=a;i>=b;i-=c)
//宏定义 
int n,m;//题目上有,不过多赘述 
ll ans;//记录答案,记得开longlong
vector<int> e;//记录每一条线段的元素 
vector<int> res;//记录每条线段上相邻元素的差值 
bool cmp(int a,int b){return a>b;}//降序排列 
int main(){
    read(n,m);//读入 
    rint a,b;
	For(i,1,n){
		read(a);//读入线段长度 
		e.clear();//记得清空先前线段 
		For(j,1,a){
			read(b);//读入线段元素 
			e.push_back(b);//压入动态数组(是叫动态数组吧) 
		}
		sort(e.begin(),e.end());//给元素排序
		For(i,1,a-1){
			res.push_back(e[i]-e[i-1]-1);//解题关键!!! 
		}
		ans+=e[a-1]-e[0]+1;//计算整体极差 
	}
	sort(res.begin(),res.end(),cmp);//降序排序 
	For(i,0,res.size()-1){
		if(i>=m-1||res[i]<=0) break;//超出允许次数或无法再删就跳出 
		ans-=res[i];//对应上面整体减空白 
	}
	write(ans);//输出答案 
    return 0;
}
//over~~

AC记录。

最后注明几点：

题解：P11639 Line Game

文章操作

题目链接：P11639 Line Game。

个人见解：

进入正题：

题目大意：

题目简化：

题目分析：

注意事项：

Code呈现：

1. he码的 oier 不是好 oier。

2. 鄙人第一次写题解，不喜勿喷。

3. 如有 hack 数据或内容有误，欢迎指出。

结尾鸣谢:

感谢 K_J_M 大佬和 co7ahang 大佬抽出他们宝贵的时间帮我微调。

相关推荐

评论

题解：P11639 Line Game