站外题求助

题目:助教孙吴最近深深的困扰于给同学们出题这个任务，因为一套题既不能都太难，也不能太简单，因此他希望这套题能够做到在难度上是平衡的。

假设一套题目中有n道题目，对于第i道题目有一个难度系数k_i。我们称一套题目的难度是平衡的当且仅当对于连续的两道编号为a和a+1的题目，其难度系数的差值的绝对值应当小于等于一个平衡系数X。

例如当平衡系数是2的时候，1 1 1 2为一套平衡的题目，1 1 1 4是一套不平衡的题目。

现在助教孙吴出好了一套题，共计有n道题目，但他出题的时候压根没想过这么多事情，因此这套题目很可能是不平衡的，他希望聪明的你能够帮助他整理题目。我们至少需要从中删除掉多少道题目才能使得这套题目恢复平衡性呢?你可以对题目的顺序进行重新排列

测试用例：

输入：

5 3

1 9 5 3 10

输出：2

我的思路

计算出每个相邻的差值，然后如果比k大，找出它距离排头与排尾的较小值，最后去找出其中最大值。这样做的话只能删一头，如果要删两头该怎么办呢？

我的代码

#include<stdio.h>
#include <algorithm>//用sort加的头文件 
using namespace std;
int main()
{
	int n,A[10000],k,C[10000],T[10000],t=0;
	scanf("%d %d",&n,&k);
	for(int i=0;i<n;i++)	scanf("%d",&A[i]);
	sort(A,A+n);//从小到大排序
	for(int i=0;i<n-1;i++)	
	{
		C[i]=(A[i+1]-A[i]);
		if(C[i]>k)	T[i]=min(i,(n-i-1));
	}
	for(int i=0;i<n-1;i++)	t=max(T[i],t);
	printf("%d",t);
	return 0;
}

讨论操作

我的思路

我的代码

回复

相关推荐

站外题求助