#C231113A. 项链(necklace)

标签（Label）

• 贪心

• 二分答案

网址（Website）

$\qquad$ 题目详情 - 项链(necklace) - Super

$\qquad$ 题解 - 项链(necklace) - Super

题解（Solution）

$\qquad$看见最大最小，直接想可不可以二分答案，很明显，可以。

$\qquad$对于每一个 $mid$ ，如果项链上有两个数之和大于 $mid$ ，那么直接删掉最大的，做完了。

代码（Code）

#include<bits/stdc++.h>
#include<deque>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int N = 501234;
bool ST;
int tid,n,m,a[N];
int maxs;
deque<int> q;
inline bool check(int mid){
        while(q.size()) q.pop_back();
	For(i,1,n){
		if(q.empty()){q.emplace_back(a[i]);continue;}
		int x=q.back();q.pop_back();int y=a[i];
		if(x+y>mid) q.emplace_back(min(x,y));
		else q.emplace_back(x),q.emplace_back(y);
	}if(q.size() && q.front()+q.back()>mid){
		if(q.front()>q.back()) q.pop_front();else
		if(q.front()<=q.back()) q.pop_back();
	}return q.size()==m?2:q.size()>m;
}

inline int Erfen(){//记得处理环的情况 
	int l=0,r=maxs,res=-1,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)) res=mid,r=mid-1;
		else l=mid+1;
	}return res;
}

bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n"; 
	string str("necklace");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	cin>>tid>>n>>m;For(i,1,n) a[i]=input(),maxs+=a[i];
	return cout<<Erfen()<<'\n',0;
}

后续（Ending）

$\qquad$明白为什么写挂了：

if(q.front()>q.back()) q.pop_front();
if(q.front()<=q.back()) q.pop_back();

$\qquad$应该为：

if(q.front()>q.back()) q.pop_front();else
if(q.front()<=q.back()) q.pop_back();

$\qquad$之后做题要考虑到每个并列的判断互相影响的情况，一定要注意！