【作业向】程序设计思维与实践 Week4 作业

发表于 | 分类于 ，
字数统计: 2k | 阅读时长 ≈ 9

【作业向】程序设计思维与实践 Week4 作业

♔A DDL 的恐惧

♔Problem

ZJM 有 n 个作业，每个作业都有自己的 DDL，如果 ZJM 没有在 DDL 前做完这个作业，那么老师会扣掉这个作业的全部平时分。

所以 ZJM 想知道如何安排做作业的顺序，才能尽可能少扣一点分。

请你帮帮他吧！

♔Input

输入包含T个测试用例。输入的第一行是单个整数T，为测试用例的数量。

每个测试用例以一个正整数N开头(1<=N<=1000)，表示作业的数量。

然后两行。第一行包含N个整数，表示DDL，下一行包含N个整数，表示扣的分。

♔Output

对于每个测试用例，您应该输出最小的总降低分数，每个测试用例一行。

♔Example

♔Input

1
2
3
4
5
6
7
8
9
10
3
3
3 3 3
10 5 1
3
1 3 1
6 2 3
7
1 4 6 4 2 4 3
3 2 1 7 6 5 4

♔Output

1
2
3
0
3
5

♔Hint

上方有三组样例。

对于第一组样例，有三个作业它们的DDL均为第三天，ZJM每天做一个正好在DDL前全部做完，所以没有扣分，输出0。

对于第二组样例，有三个作业，它们的DDL分别为第一天，第三天、第一天。ZJM在第一天做了第一个作业，第二天做了第二个作业，共扣了3分，输出3。

♔解题思路

由题意得，本题要求扣除的最少分数，可以转化为得到的最多分数。使用贪心求解，策略为按照分数降序排序，从分数最高的事件进行遍历。处理每一个事件时，从DDL开始往前遍历，把该事件放到遇到的第一个空闲的时间，并获得该事件的分数。当所有事件遍历结束之后，用总分数减去获得的分数即为减去的分数。

♔代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#define ll long long
using namespace std;
struct data
{
	int t,p;
}ddl[10005];
int n,T,ans;
int visit[10005];

int wly(data a,data b)
{
	return a.p<b.p;
}

int main()
{
	int i,j;
	scanf("%d",&T);
	while(T--)
	{
		ans=0;
		memset(visit,0,sizeof(visit));
		scanf("%d",&n);
		for(i=1;i<=n;i++) scanf("%d",&ddl[i].t);
		for(i=1;i<=n;i++) scanf("%d",&ddl[i].p);
		sort(ddl+1,ddl+1+n,wly);
		for(i=n;i>0;i--)
		{
			j=ddl[i].t;
			while(visit[j] && j>0) j--;
			if(j) visit[j]=1;
			else ans+=ddl[i].p;
		}
		printf("%d\n",ans);
	}
	return 0;
}

♔B 四个数列

♔Problem

ZJM 有四个数列 A,B,C,D，每个数列都有 n 个数字。ZJM 从每个数列中各取出一个数，他想知道有多少种方案使得 4 个数的和为 0。

当一个数列中有多个相同的数字的时候，把它们当做不同的数对待。

请你帮帮他吧！

♔Input

第一行：n（代表数列中数字的个数） （1≤n≤4000）

接下来的 n 行中，第 i 行有四个数字，分别表示数列 A,B,C,D 中的第 i 个数字（数字不超过 2 的 28 次方）

♔Output

输出不同组合的个数。

♔Examples

♔Input

1
2
3
4
5
6
7
6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

♔Output

1
5

♔Hint

样例解释: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).

♔解题思路

从题目的数据范围我们可以得知我们需要使用二分的方法，对于前两个和后两个数组，我们分别求出他们中各个元素的和，于是我们可以得到两个大小为2n的数组。我们先将将其中一个数组A按升序排序，对于另一个数组B，从第一个元素开始遍历，并在数组A中用二分的方式找到等于-B[i]的元素的位置，并统计值等于-B[i]的元素个数。由此我们可以得到所有方案的个数。

♔代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#define ll long long
using namespace std;
int n,ans;
int a[4005][4],sum1[16000005],sum2[16000005];

int make(int x)
{
	int l=0,r=n*n-1;
	int mid=(l+r)/2;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(sum2[mid]==-x)
		{
			int i,sum=0;
			for(i=l;i<=r;i++) 
				if(sum2[i]==-x) sum++;
			return sum;
		}
		else if(sum2[mid]<-x) l=mid+1;
		else r=mid-1;
	}
	return 0;
}

int main()
{
	int i,j;
	scanf("%d",&n);
	for(i=0;i<n;i++) scanf("%d%d%d%d",&a[i][0],&a[i][1],&a[i][2],&a[i][3]);
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			sum1[i*n+j]=a[i][0]+a[j][1],sum2[i*n+j]=a[i][2]+a[j][3];
	sort(sum2,sum2+n*n);
	for(i=0;i<n*n;i++)
	{
		ans+=make(sum1[i]);
	}
	printf("%d",ans);
	return 0;
}

♔C TT 的神秘礼物

♔Problem

TT 是一位重度爱猫人士，每日沉溺于 B 站上的猫咪频道。

有一天，TT 的好友 ZJM 决定交给 TT 一个难题，如果 TT 能够解决这个难题，ZJM 就会买一只可爱猫咪送给 TT。

任务内容是，给定一个 N 个数的数组 cat[i]，并用这个数组生成一个新数组 ans[i]。新数组定义为对于任意的 i, j 且 i != j，均有 ans[] = abs(cat[i] - cat[j])，1 <= i < j <= N。试求出这个新数组的中位数，中位数即为排序之后 (len+1)/2 位置对应的数字，’/’ 为下取整。

TT 非常想得到那只可爱的猫咪，你能帮帮他吗？

♔Input

多组输入，每次输入一个 N，表示有 N 个数，之后输入一个长度为 N 的序列 cat， cat[i] <= 1e9 , 3 <= n <= 1e5

♔Output

输出新数组 ans 的中位数

♔Examples

♔Input

1
2
3
4
4
1 3 2 4
3
1 10 2

♔Output

1
2
1
8

♔解题思路

该题是要我们求出 abs(cat[i] - cat[j])，1 <= i < j <= N的中位数。我们可以将cat数组按升序进行排序，以此来达到去绝对值的目的。然后使用二分答案，对于二分到的每一mid求出他们在abs(cat[i] - cat[j])中的排名，以此来判断他们是否是中位数。在求排名的时候我们同样使用二分的方法可以进一步降低复杂度。求排名的做法为对于每一个cat[i],在cat[i+1]到cat[n]中通过二分来求出abs(cat[i] - cat[j])=mid的第一个位置，以此求得有多少abs(cat[i] - cat[j])小于mid，然后将结果加一即为mid在abs(cat[i] - cat[j])中的排名。通过这种方法，我们就可以以O（n longn longn）的复杂度解决这个问题。

♔代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#define ll long long
using namespace std;
int n,cat[100005];

int judge(int x)
{
	int mid,l,r;
	int sum=0;
	for(int i=1;i<n;i++)
	{
		l=i+1,r=n;
		while(l<=r)
		{
			mid=(l+r)/2;
			//printf("%d %d %d %d\n",l,r,cat[mid],cat[i]);
			if(cat[mid]-cat[i]<x) l=mid+1;
			else r=mid-1;
		}
		sum+=l-1-i;
		//printf("--%d %d--\n",l,i);
	}
	//printf("+%d %d+\n",x,sum);
	return sum;
}

int main()
{
	int i,j;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=1;i<=n;i++) scanf("%d",&cat[i]);
		sort(cat+1,cat+1+n);
		int mid,l=0,r=cat[n];
		while(l<=r)
		{
			//printf("%d %d\n",l,r);
			mid=(l+r)/2;
			if(judge(mid)+1<=(((n-1)*n/2+1)/2)) l=mid+1;
			else r=mid-1;
		}
		printf("%d\n",l-1);
	}
	return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！