现有 A、B 两队进行篮球比赛,位置 d 为三分线,在三分线外进球则得 3 分,三分线内进球则得 2 分;

设 A 队整场进球 n 个,位置分别为 a1,a2,…an
设 B 队整场进球 m 个,位置分别为 b1,b2,…bm

主人公小明有权设立三分线位置,他想让 A 队尽可能多的得分,以拉大 A、B 两队的得分差距。

问将 d 设置为多少可以使得 Score(A)−Score(B) 分差最大?

3 4 收藏


直接登录
最新评论
  • wohenshuai   2015/11/29

    思路:设A队投进的球记为圆形,B队投进的球记为三角形。三分线的位置即圆弧的设置位置,为使问题简化,可以将A,B两队所有投进点沿圆弧移动,使得三角形和圆形在以篮筐为起点的同一射线上。这样不管n和m的关系如何,都是在找三分线外,使得圆形的个数和三角形的个数差值最大。要是编起程来还是很麻烦的,最简单的就是依次遍历记录差值了。

  • 廖仑辉   2015/11/29

    怎么设置都不行,毫无根据

  • RayHoward   2015/11/30

    用结构数组储存数据。结构包含以下元素:队名,距离。对数组按距离进行降序排列。新建两个变量Gap和MaxGap。对数组进行遍历,A队Gap++,B队Gap–,更新MaxGap并记录数组data[k]的下标k。
    当然这里有个问题是如果距离有相同的,即ai=bj,要特殊处理。
    最后data[k]与data[k+1](如果k+1不越界)两距离组成的开区间就是所求d的设置范围。

  • __ZhW__   2015/11/30

    简述一下个人想到的DP解法:
    可以把AB数组合并后排序形成数组C,并新开一个数组D来标记C中的某元素原先是在A中还是B中在A中为1在B中为-1。(将排序中加入对C的操作可以在nlogn时间完成,D[i] = 1 if C[i] is in A else -1)。
    首先,如果dC[m+n],则两者每球得分相同,总分差距为(n-m),作为我们的备选方案1,对应的解为dC[m+n]其中之一。
    此后,我们只需要考虑d的位置在C范围以内(c[1]<d<=C[m+n])。若C[k-1]<d<=C[k] 则两者得分等价于将d设置在C[k]处,因此这个问题可以转化为:找到合适的index k来使得D[i]及其之后的元素中,(A元素数量-B元素数量)最大。
    解决上述问题可以采用DP方法:
    新开一个数组E来保存“在数组D中D[k]及其后面所有元素中A元素数量(1的数量)-B元素数量(-1的数量)”,这一E的定义就是我们前面要把D数组元素设为1与-1的原因,有了上述条件不难写出DP方程:
    E[i] = E[i+1] + D[i],其中边界条件E[m+n]=D[m+n]
    最后,通过线性扫描一遍E数组,找到其中的最大值E[k],对应的d=C[k]便是方案2的解,E[k]便是最大的scoreA-scoreB,将E[k]与n-m比大小,返回更大的方案对应的解便是最终方案。
    复杂度=O(nlogn)+O(n) = O(nlogn)
    ps:可能有多个最优解,上述算法返回其中之一。

  • __ZhW__   2015/11/30

    简述一下个人想到的DP解法:
    可以把AB数组合并后排序形成数组C,并新开一个数组D来标记C中的某元素原先是在A中还是B中在A中为1在B中为-1。(将排序中加入对C的操作可以在nlogn时间完成,D[i] = 1 if C[i] is in A else -1)。
    首先,如果d>C[m+n] or d<=C[1],则两者每球得分相同,总分差距为(n-m),作为我们的备选方案1,对应的解为dC[m+n]其中之一。
    此后,我们只需要考虑d的位置在C范围以内(c[1]<d<=C[m+n])。若C[k-1]<d<=C[k] 则两者得分等价于将d设置在C[k]处,因此这个问题可以转化为:找到合适的index k来使得D[i]及其之后的元素中,(A元素数量-B元素数量)最大。
    解决上述问题可以采用DP方法:
    新开一个数组E来保存“在数组D中D[k]及其后面所有元素中A元素数量(1的数量)-B元素数量(-1的数量)”,这一E的定义就是我们前面要把D数组元素设为1与-1的原因,有了上述条件不难写出DP方程:
    E[i] = E[i+1] + D[i],其中边界条件E[m+n]=D[m+n]
    最后,通过线性扫描一遍E数组,找到其中的最大值E[k],对应的d=C[k]便是方案2的解,E[k]便是最大的scoreA-scoreB,将E[k]与n-m比大小,返回更大的方案对应的解便是最终方案。
    复杂度=O(nlogn)+O(n) = O(nlogn)
    ps:可能有多个最优解,上述算法返回其中之一。

  • 维妙伟小德   2015/11/30

    差距就是abs(functionA(d)*n-functionB(d)*n)。当d由0逐渐变大时最多会有m+n+1类取值区分两队有效进球的得分情况,只需要循环取每种情况的abs(functionA(d)*n-functionB(d)*n)取最大值即可

  • 御风行   2015/11/30

    以球场中下点为坐标轴,A队和B队的投射点所形成的线为A(x)和B(x),三分线d得到了两个点a,b,并且a=-b,
    当xa时,M(x)=3*A(x);当xb时,N(x)=2*B(x),
    求此值a使得M(x)-N(x)最大

  • 题目都没问清楚,这个三分线可以是什么形状?我不懂篮球,如果是半圆的话,我觉得可以将距投篮位置转换成距离,然后将所有投篮位置的距离排个序(包括A队和B队),然后按照这个距离从小到大开始依次枚举。因为最开始A队是3n分,B队是3m分,所以枚举的时候只需要知道当前枚举点往前有几个进球是A队的,几个是B队的就好,得分减掉个数,就是成绩,然后取最大值就好。
    复杂度:O(n+m)+O((n+m)log(n+m))+O(n+m) = O((n+m)log(n+m))

    错误之处,还望指正。

  • 王先生 学生 2015/11/30

    分析

    此题要求 Score(A)−Score(B) 的最大值,就要保证 A 队得分尽量高,也就是说要使得其三分球的数目尽可能的多。现在以 A 队投篮的位置为基准,将三分线设立为其从小到大的逐个位置,求分差,找到最大分差值,则该位置就是三分线设立点。

    程序实现

    #include
    #include
    #include
    #include
    using namespace std;
    int getCount(vector &Bd, int m, int d)
    {
    int count = 0;
    for (int i = 0; i < m; i++)
    {
    if (Bd[i] < d)
    count++;
    }
    return count;
    }

    int maxScore(vector &Ad, int n, vector &Bd, int m)
    {

    //将AB两队的,投篮点排序
    sort(Ad.begin(), Ad.end());
    sort(Bd.begin(), Bd.end());
    int max = 0 , dis = 0;
    for (int i = 0; i max)
    {
    max = tmp;
    dis = d;
    }//if
    }
    return max;
    }

    int main()
    {
    int n, m,tmp;
    vector Ad, Bd;

    cin >> n;
    for (int i = 0; i > tmp;
    Ad.push_back(tmp);
    }
    cin >> m;
    for (int i = 0; i > tmp;
    Bd.push_back(tmp);
    }

    cout << maxScore(Ad, n, Bd, m) << endl;
    system("pause");
    return 0;
    }

  • SJ君 求职 2015/12/01

    //第一步,对输入的长度n的一维数组double[] an 和长度为m的一维数组double[] bm进行排序
    sort(an);
    sort(bn);

    //第二步,写lessThanD函数,输入数组和d,会遍历数组返回比d小的数的数目。
    public int lessThanD(double[] a, double d) {
    int n = a.length;
    int count = 0;
    for (int i = 0; a[i] < d; i++) {
    count++;
    }
    return count;
    }

    //第三步,确定d的最大范围max(an[n-1],bm[m-1])
    double maxD = Math.max(an[n – 1], bm[m – 1]);

    //第四步,写fenCha函数,输入an bm两个数组,会让d从0到max循环,获取最大分差,最后返回最大分差时的d
    public int fenCha(double[] an, double[] bm) {
    int n = an.length;
    int m = bm.length;
    int index = 0;//记录d
    int max = 0;//存储最大分差
    for (int d = 0; d max){
    max = ScoreA_ScoreB;
    index = d;
    }
    }
    return index;
    }

  • 经济抠门男   2015/12/02

    俩数组分别排序后,进行一次归并排序,在归并的过程中实时计算最大差值,归并完了也就算完了,挺简单的

  • public static void main(String[] args) {
    //以球框位置为圆心,设三分线位置、投球位置为距球框距离
    int d = 0;//三分线位置
    int j = 20;//三分线最大位置
    int score = 0;//两队相差最大分数
    int lin = 0;//临时最大分数
    int[] A = {};//A队投篮位置数组
    int[] B = {};//B队投篮位置数组
    //以最大三分线位置逐级递减
    for(int l = j;l>0;l–){
    int a3 = 0;//A队三分球数量
    int b3 = 0;//B队三分球数量
    int M = A.length;//A队投球个数
    int N = B.length;//B队投球个数
    //得到当前三分线位置A队获得三分球数量
    for(int a : A){
    if(a>l){
    a3++;
    }
    }
    //得到当前三分线位置B队获得三分球数量
    for(int b : B){
    if(b>l){
    b3++;
    }
    }
    //计算A队所得分数
    int aSc = a3*3+(M-a3)*2;
    //计算B队所得分数
    int bSc = b3*3+(N-b3)*2;
    if(aSc>bSc){
    //如果A队分数大于B队分数,求分差
    score = aSc-bSc;
    if(score>lin){
    //如果该分差大于当前最大分差,则给当前最大分差附上该值,并记录当前三分线位置d
    lin = score;
    d = l;
    }
    }
    }
    //d 的位置可能非唯一只,可以 将d设为数组,将每一次A分大于B分的距离记录下来,再求数组中的最大值
    System.out.println(“最佳距离:”+d);
    }

  • I_O_O 码农 2015/12/03

    思路:设A球队进入了x个三分,B球队进入了y个三分。则两队分差值为:3(x-y)+2(n-x)-2(m-y) = (x-y) + 2(n-m);. 要让差值最大,只需要x-y达到最大。
    类比:对于a数组,b数组进行合并后得到排序数组c。只需要找到一个分界点d,使得大于d的a数组个数是x,b数组个数为y ,且max(x-y);

  • Bill Liu   2015/12/08

    Arrays.sort(a);
    Arrays.sort(b);
    int maxIndex = n>m?m:n;
    int d=0;
    for(int i=0;ib[i])
    d = a[i];
    }