求证正解正确性
查看原帖
求证正解正确性
640816
cengzh楼主2024/9/26 19:49

rt,本人做法贪心但W了(太菜了)

但是看了题解后又感觉不太理解 二分答案check中,两个电池差值如果大于当前答案x就跳过,可是无论如何这两个电池其中一个必有一个作为芯片功率,那么后来的另一个芯片功率与它的差值一定会大于这两个电池的差值,这样真的能过吗。并且二分到正确答案后check函数与贪心好像没有区别(?

贪心做法:排序好以后对每对电池作为两个芯片的功率,取最大值。

为什么不能过,求解orz

# include <stdio.h>
# include <bits/stdc++.h>

using namespace std;

int Battery[1000005];

int main (void)
{
	int n,k;
	scanf ("%d %d",&n,&k);

	for (int i=0;i<2*n*k;i++)
	{
		scanf ("%d",&Battery[i]);
	}

	sort(Battery,Battery+2*n*k);

	int ans = -1;

	for (int i=0;i<2*n;i+=2)
	{
		ans = max(ans,Battery[i+1]-Battery[i]);
	}

	printf ("%d",ans);

	return 0;
}

2024/9/26 19:49
加载中...