Codeforces Round 935 (Div.3 E F)

E. Binary Search

题意：

给出长度为n的排列，和数字x，可以交换最多两次序列中的元素，使得最终二分的答案在序列中指向的元素为x；

思路：按照题意 去模拟二分 模拟出来 l最终的位置

若 a[l]==x 则输出0 不需要

若 a[l]<x 则将 l 与x对应的下标交换 （都是小于等于x 不会影响二分的结果）

若a[l]>x 则将1与x对应的下标交换 (若a[l]>x 说明 l 一直在1处没有动 动的只是r)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=3e5+10;
ll a[N],b[N],c[N];
int main()
{
	int t;cin>>t;
	while(t--)
	{
	   int n,x;cin>>n>>x;
	   int num;
	   for(int i=1;i<=n;i++)
	   {
	   	cin>>a[i];
	   	if(a[i]==x) num=i;
	   }
	   int l=1,r=n+1;
	   while(l+1<r)
	   {
	   	 int mid=(l+r)>>1;
	   	 if(a[mid]<=x) l=mid;
	   	 else r=mid;
	   }
	   if(a[l]==x) cout<<"0"<<endl;
	   else if(a[l]<x)
	   {
	   	  cout<<"1"<<endl;
	   	  cout<<l<<" "<<num<<endl;
	   }
	   else if(a[l]>x)
	   {
	   	   cout<<"1"<<endl;
	   	   cout<<"1 "<<num<<endl;
	   }
	}
	return 0;
	
}

F. Kirill and Mushrooms

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
const int N=3e5+10;
priority_queue<ll,vector<ll>,greater<ll>>q;
struct s
{
	ll num;
	ll idx;
}stu[N];
bool cmp(s x,s y)
{
	if(x.num==y.num) return x.idx>y.idx;
	return x.num>y.num;
}
ll res;
int n;
ll a[N],b[N];
int main()
{
	int t;cin>>t;
	while(t--)
	{
	   cin>>n;
	   ll max1=0;
	   for(int i=1;i<=n;i++)
	   {
	     cin>>a[i];
		 max1=max(max1,a[i]);
	   }
	   res=max1;
	   for(int i=1;i<=n;i++) cin>>b[i];
	   for(int i=1;i<=n;i++)
	   {
	   	stu[i].num=a[b[i]];
	   	stu[i].idx=i;
	   }
	   sort(stu+1,stu+1+n,cmp);
	   int xx=1;
	   int j=1;
	   while(q.size()) q.pop();
	   for(int k=1;k<=(n+1)/2;k++)
	   {
	   	while(q.size()&&q.top()<=k-1) q.pop();
	   	while(q.size()<k&&j<=n)
	   	{
	   	     if(stu[j].idx<=k-1) j++;
			 else
			 {
			     q.push(stu[j].idx);
				 j++;	
			 }	
	    }
	    if(q.size()==k)
	    {
	    	ll num1=stu[j-1].num*k;
	    	if(num1>res)
	    	{
	    		res=num1;
	    		xx=k;
			}
		}
	   }
	   cout<<res<<" "<<xx<<endl;
	   
	}
	return 0;
	
}