(C卷,100分)- 求最多可以派出多少支团队
题目描述
用数组代表每个人的能力，一个比赛活动要求参赛团队的最低能力值为N，每个团队可以由1人或者2人组成，且1个人只能参加1个团队，计算出最多可以派出多少只符合要求的团队。
输入描述
第一行代表总人数，范围1-500000
第二行数组代表每个人的能力
数组大小，范围1-500000
元素取值，范围1-500000
第三行数值为团队要求的最低能力值，范围1-500000
输出描述
最多可以派出的团队数量
用例
输入 5
3 1 5 7 9
8
输出 3
说明 说明 3、5组成一队 1、7一队 9自己一队 输出3
输入 7
3 1 5 7 9 2 6
8
输出 4
说明 3、5组成一队，1、7一队，9自己一队，2、6一队，输出4
输入 3
1 1 9
8
输出 1
说明 9自己一队，输出1
题目解析
本题要求最多的组队，而组队要求是：
可以1人组队，也可以2人组队
团队的能力值之和需要大于等于最低能力minCap要求
因此，为了组更多队伍，我们应该尽量让单人组队，即：
需要将能力值大于等于minCap的筛选出来，单人组队
然后剩余的人，按照能力值升序排序，定义L,R指针，初始时L=0，R=k-1，k是剩余人总数
接着尝试L，R进行组队：
如果L，R两人的能力之和大于等于minCap，则组队成功，L++，R–
否则，说明L无法和任何人组队，因为R已经是当前最高能力的人，L无法和R组队，则也意味着无法和能力值比R低的人组队，因此L++
在上面过程中，计算出组队个数作为题解。
解法一
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a,const void *b){
return (*(int*)a)-(*(int*)b);
}
int main()
{
int n;
scanf("%d",&n);
int cap[n];
for(int i=0;i<n;i++){
scanf("%d",&cap[i]);
}
int mincap;
scanf("%d",&mincap);
qsort(cap,n,sizeof(int),cmp);
int l=0;
int r=n-1;
int ans=0;
while(l<=r&&cap[r]>=mincap){
r--;
ans++;
}
while(l<r){
if(cap[l]+cap[r]>=mincap){
r--;
l++;
ans++;
}
else
l++;
}
printf("%d",ans);
return 0;
}
解法二
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a,const void *b){
return (*(int*)a)-(*(int*)b);
}
int main()
{
int n;
scanf("%d",&n);
int cap[n];
for(int i=0;i<n;i++){
scanf("%d",&cap[i]);
}
int mincap;
scanf("%d",&mincap);
qsort(cap,n,sizeof(int),cmp);
int l=0;
int r=n-1;
int ans=0;
while(l<r){
if(cap[l]+cap[r]==mincap){//最轻和最重的人可以坐一辆车l++，r--
l++;
}
r--;//否则，最重的人自己一辆车
ans++;
}
printf("%d",ans);
return 0;
}
(C卷,100分)- 部门人力分配
题目描述
部门在进行需求开发时需要进行人力安排。
当前部门需要完成 N 个需求，需求用 requirements 表述，requirements[i] 表示第 i 个需求的工作量大小，单位：人月。
这部分需求需要在 M 个月内完成开发，进行人力安排后每个月人力时固定的。
目前要求每个月最多有2个需求开发，并且每个月需要完成的需求不能超过部门人力。
请帮助部门评估在满足需求开发进度的情况下，每个月需要的最小人力是多少？
输入描述
输入为 M 和 requirements，M 表示需求开发时间要求，requirements 表示每个需求工作量大小，N 为 requirements长度，
1 ≤ N/2 ≤ M ≤ N ≤ 10000
1 ≤ requirements[i] ≤ 10^9
输出描述
对于每一组测试数据，输出部门需要人力需求，行末无多余的空格
用例
输入 3
3 5 3 4
输出 6
说明
输入数据两行，
第一行输入数据3表示开发时间要求，
第二行输入数据表示需求工作量大小，
输出数据一行，表示部门人力需求。
当选择人力为6时，2个需求量为3的工作可以在1个月里完成，其他2个工作各需要1个月完成。可以在3个月内完成所有需求。
当选择人力为5时，4个工作各需要1个月完成，一共需要4个月才能完成所有需求。
因此6是部门最小的人力需求。
题目解析
本题是将二分和双指针考点结合在了一起。
#include <stdio.h>
#include <stdlib.h>
long long cmp(const void *a,const void *b){
return (*(long long*)a)-(*(long long*)b);
}
int check(long long mid,int m,int* req,int len){
int i=0;
int j=len-1;
int count=0;
while(i<=j){
if(req[i]+req[j]<=mid){//如果最轻的人和最重的人可以共享一辆车，则l++,r--
i++;
}
j--;//否则最重的人只能单独坐一辆车，即仅r--
count++;
}
return count<=m;
}
long long getResult(int m,int* req,int len){
qsort(req,len,sizeof(int),cmp);
long long min=req[len-1];
long long max=req[len-1]+req[len-2];
while(min<=max){
long long mid=(min+max)/2;
if(check(mid,m,req,len)){
max=mid-1;
}
else{
min=mid+1;
}
}
return min;
}
int main()
{
int m;
int req[10000];
int len=0;
scanf("%d",&m);
while(scanf("%d",&req[len++])){
if(getchar()!=' ')break;
}
printf("%lld\n",getResult(m,req,len));
return 0;
}
