欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018 09.23 挖掘机(二分答案)

程序员文章站 2022-05-08 17:44:11
...

描述

派了一群疯狂伊文成功摧毁敌军的碉堡后, L终于得到了他想要的挖掘机,于是开始 情不自禁地挖掘。
L依旧把地面看作连续的 N 个格子。由间谍传回的情报,敌军在这些格子中的每一个 里都埋有一颗地雷,且第 i 格中地雷的种类为 ti。 ti 为一个 1 到 M 之间的整数,并且第 i 类雷 的重量均为 wi。
为了为我军的坦克开辟前进的道路,当然也为了使用自己的挖掘机, L 开始愉快地扫 雷(确切地说是挖雷)。
L会事先选择好 L; R(1 6 L 6 R 6 N),然后从第 L 个格子出发开到第 R 个格子,边 开边挖地上的雷。 Mr.Lin 喜欢新奇之物,假如当前挖出的雷不与之前挖出的任何一颗雷属于同 一类,他就会把这颗雷收藏起来。否则,他会把地雷拆解回收。
不过, L 现在还没有想好合适的 L 和 R。他的幸运数字是 k,于是希望你帮他选择合 适的 L; R 使得最后收藏的雷的重量之和为所有方案中第 k 大。

输入

第一行两个正整数 N; M 分别表示格子数和地雷的种数。
第二行 M 个正整数 wi。
第三行 N 个正整数 ti。
第四行一个正整数 k,表示L的幸运数字。

输出

第一行一个整数为收藏的雷的总重量。
第二行两个正整数为满足条件的 L 和 R。如果有多个满足条件的 L; R,输出字典序最小的
(即第一关键字为 L,第二关键字为 R)。

样例输入

3 2
1 2
1 2 1
2

样例输出

3
1 2

提示

对于 20% 的数据, N; M <=100。
对于 40% 的数据, N; M <= 1000。
另有 20% 的数据, k <= 10^5。
对于 100% 的数据, 1 <= N; M <= 10^5; 1 <= wi <= 10^9; 1 <= ti <= M; 1 <= k <= (1+N )*N/2


一道很好的二分答案。
考虑二分第k个值是val的时候如何检验。
我们可以借用双指针的思想来统计有多少个数不小于val。
然后通过跟k比较来判断是否合法,最后再次使用双指针的思想找到字典序最小的区间就行了。
代码:

#include<bits/stdc++.h>
#define N 100005
#define ll long long
using namespace std;
inline ll read(){
	ll ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
ll w[N],l=0,r=0,k,ret,tot,ans;
int pos,col[N],pre[N],n,m;
bool in[N];
inline ll check(ll val){
	tot=0,pos=1,ret=0,memset(in,false,sizeof(in)),memset(pre,0,sizeof(pre));
	for(int i=1;i<=n;++i){
		if(pre[col[i]]<pos)tot+=w[col[i]];
		in[pre[col[i]]]=false,in[(pre[col[i]]=i)]=true;
		while(tot>=val&&pos<=i)tot-=in[pos]*w[col[pos++]];
		ret+=pos-1;
	}
	return ret;
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=m;++i)r+=(w[i]=read());
	for(int i=1;i<=n;++i)col[i]=read();
	k=read();
	while(l<=r){
		ll mid=l+r>>1;
		if(check(mid)<k)r=mid-1;
		else l=mid+1,ans=mid;
	}
	cout<<ans<<'\n',tot=0,pos=1,ret=0,memset(in,false,sizeof(in)),memset(pre,0,sizeof(pre));
	for(int i=1;i<=n;++i){
		if(pre[col[i]]<pos)tot+=w[col[i]];
		in[pre[col[i]]]=false,in[(pre[col[i]]=i)]=true;
		while(tot>ans&&pos<=i)tot-=in[pos]*w[col[pos++]];
		if(tot==ans){cout<<pos<<' '<<i;return 0;}
	}
	return 0;
}