Codeforces Round #737 (Div. 2)

A.Ezzat and Two Subsequences

Difficulty\mathtt{Difficulty}=800\mathtt{800}
看完题目后，我们并不知道最优解该如何构造
然后我们观察样例及解释：

  • 第一组，最终是 {1,2}\{1,2\} 和 {3}\{3\}
  • 第二组，最终是 {−6,−7}\{-6,-7\} 和 {−6}\{-6\}

然后我们不难得到一个猜想：

将最大的数单独为一组，其余为一组

代码实现简单
至于证明，我有一个很妙的解法，但是这里太小了，写不下😆

#include<bits/stdc++.h>
#define BetterIO ios::sync_with_stdio(false)
using namespace std;
int N,A[100001];
#define int long long
main(void)
{
	BetterIO;
	register int Case;cin>>Case;while(Case--)
	{
		register int i;cin>>N;
		for(i=1;i<=N;i++)cin>>A[i];
		sort(A+1,A+N+1);
		register int Sum=0;
		for(i=1;i<N;i++)Sum+=A[i];
		printf("%.9lf\n",1.0*Sum/(N-1)+1.0*A[N]);
	}
	return 0;
}

B.Moamen and k-subarrays

Difficulty\mathtt{Difficulty}=1100\mathtt{1100}
看完题目后，我们得到一个猜想：

只要将原串分成递增的小段即可

但是我们轻而易举地 hackhack 掉了
比如说前面有一个 {3,6}\{3,6\} 后面有一个 {4}\{4\} 就炸掉了
于是我们稍加改进，不难得到：

只要将原串分成递增的小段且是排完序紧挨的即可

然后可以用 pair 来优化写法，于是代码不难写出

#include<bits/stdc++.h>
#define BetterIO ios::sync_with_stdio(false)
using namespace std;
int N,K,A[100001];
pair< int,int >B[100001];
int main(void)
{
	BetterIO;
	register int Case;cin>>Case;while(Case--)
	{
		register int i;cin>>N>>K;
		for(i=1;i<=N;i++)cin>>A[i];
		for(i=1;i<=N;i++)B[i].first=A[i],B[i].second=i;
		sort(B+1,B+N+1);
		register int Ans=0;
		for(i=2;i<=N;i++)if(B[i].second!=B[i-1].second+1)Ans++;
		if(Ans<K)puts("YES");
		else puts("NO");
	}
	return 0;
}