找不着原题了。

原题大概就是给你一条直线上n个点需要被覆盖的最小次数和m条需要花费1的线段的左右端点和1条[1,n]的每次花费为t的大线段。

问最小花费使得所有点的覆盖数都达到最小覆盖数。

 

感觉这个函数的斜率是单调的，所以就码了一个二分斜率。

 

#include
     
      #define ll long long#define maxn 100005using namespace std;const ll inf=1ll<<62ll;struct lines{	int l,r;	bool operator <(const lines &U)const{		return l==U.l?r>U.r:l
      
       rig){		b[++cnt]=a[i];		rig=a[i].r;	}		for(int i=1;i<=n;i++){		ri=max(ri,p[i]);		if(i
       
        b[cnt].r) bt=max(bt,p[i]);	}} inline ll calc(int x){	if(x
        
         >1;		if(calc(mid)-calc(mid-1)<0) an=mid,le=mid+1;		else ri=mid-1;	}		printf("%lld\n",calc(an));}int main(){	freopen("C.in","r",stdin);	freopen("C.out","w",stdout);		scanf("%d%d%d",&n,&m,&t);	for(int i=1;i<=n;i++) scanf("%d",p+i);	for(int i=1;i<=m;i++) scanf("%d%d",&a[i].l,&a[i].r);		prework();	solve();		return 0;}