首页 > 试题广场 >

年会抢玩偶游戏

[编程题]年会抢玩偶游戏

热度指数：557 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

某公司年会上，组织人员安排了一个小游戏来调节气氛。游戏规则如下：

N个人参与游戏，站成一排来抢工作人抛来的M个小玩偶。为了增加游戏的趣味和难度，规则规定，参与游戏的人抢到的礼物不能比左右两边的人多两个或以上，否则会受到一定的惩罚。游戏结束时拥有玩偶最多的人将获得一份大奖。

假设大家都想赢得这份大奖，请问站在第K个位置的小招在赢得游戏时，最多能拥有几个玩偶？

输入描述:

输入为用空格分隔的3个正整数，依次为：参与游戏人数N、玩偶数M、小招所在位置K

输出描述:

输出为1个正整数，代表小招最多能够拥有的玩偶数。若没有，则输出0。

示例1

输入

1 1 0

输出

示例2

输入

1 3 1

输出

算法知识视频讲解

元暗

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int K = scanner.nextInt();
        int[] person = new int[N];
        if (K <= 0 || N <= 0 || M <= 0||K>N) {
            System.out.println(0);
            return;
        }
        for (int i = 0; i < M; i++) {
            Add(person, K - 1);
        }
        System.out.println(person[K - 1]);
    }

    private static void Add(int[] person, int k) {
        if (k - 1 >= 0 && person[k] > person[k - 1]) {
            Add(person, k - 1);
        } else if (k + 1 < person.length && person[k] > person[k + 1]) {
            Add(person, k + 1);
        } else {
            person[k]++;
        }
    }
}

发表于 2018-04-07 09:16:21 回复(1)

尹健

#include <iostream>
using namespace std; 
int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    int s = ((n - k + 1)*(n - k) >> 1) + (k * (k - 1) >> 1); 
    if (n && (k>=1 && k<=n &&(m+s)>=max(k-1,n-k)*n)
    {
        //int s = ((n - k + 1)*(n - k) >> 1) + (k * (k - 1) >> 1); //*、+优先级大于>>
        for (int i = 0; i < n; i++)
        {
            if ((m + s - i) % n == 0)
            {
                cout << (m + s - i) / n << '\n';
                break;
            }
        }
    }
    else cout << "0" << '\n';
    return 0;
}

图片说明

三角形必须是等腰直角三角形，这样才能保证相邻位置靠近位置k的员工比k位置远的员工领到的玩偶数目多。设三角形边长为x，f(x)代表玩偶数目，递推公式f(x)=f(x-1)+x，得到f(x)=x*(x+1)/2；

位置k的员工领p个玩偶，理想情况下正好领完m个玩偶，即曲线阴影部分为m，加上直线阴影部分的糖果数s=((n - k + 1)(n - k) /2) + (k (k - 1) /2)等于n*p，即长方形部分。

如果多出来i个玩偶的话，显然只需要考虑i小于n了，否则每个人就能多发一颗糖果还能有剩。这i个玩偶已经不能发给k位置的员工了，只能从边上开始发，一人一个。那反过来求得的p就是代码中的 (m + s - i) / n。

如果玩偶数不够发，即两个梯形的顶边有个变成0还不能维持，数学公式是m<max(k-1,n-k)*n-s，这时候无解，不过测试用例没这种情形。

编辑于 2018-08-15 10:55:00 回复(11)

phlirock

include<bits/stdc++.h>
define frp(i,a,b) for(int i = a; i <= b; i++)
define clr(a,b) memset(a,b,sizeof(a))

	using namespace std;
typedef long long lint;
int n,m,k,ans = 0;
inline void get_ready( )
{
scanf("%d%d%d", &n,&m,&k);
}



	inline void solve( )
{
if(k < 1 || k > n){
puts("0");
return;
}
if(n == 1){
printf("%d\n",m);
return;
}
if(n == 2){
printf("%d\n",(m-1)/2+1);
return;
}
if(k == 1 || k == n){
printf("%d\n",(m-1)/2+1);
}
else{
int tmp = min(k,n-k);
if(tmptmp >= m){
while(tmptmp > m) tmp--;
printf("%d\n",tmp);
}
else{
int res = k+k-1,res2 = tmp*tmp;
while(res<n){ if(res2 < m){ res2+=res; tmp++; } if(res2>=m){
if(res2 == m) printf("%d\n",tmp);
else printf("%d\n",tmp-1);
return;
}
res++;
}
while(res2<m){ res2+=n; tmp++; if(res2>=m){
if(res2 == m) printf("%d\n",tmp);
else printf("%d\n",tmp-1);
}
}
}
}
}



	int main( )
{
get_ready( );
solve( );
return 0;
}

编辑于 2018-03-24 16:11:54 回复(0)

xcxcasdfsdf

设K位置有x个礼物，K左边和右边都是差1的等差数列，用公式算出和来等于M。
把x化简就算出来了。

编辑于 2018-03-29 16:37:35 回复(7)

Java

刀俎55

import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner input = new Scanner(System.in);
while(input.hasNext()){
int N = input.nextInt();
int M = input.nextInt();
int K = input.nextInt();
int result;
result = getK(N,M,K);
System.out.println(result);
}
}

public static int getK(int n,int m,int k){
int max;
if(n<=0 || m<=0 || k<=0 || k>n){
return 0;
}

for(max=0;max<=m;max++){
int sum = 0;
for(int i = 1;i<k;i++){ //把排在他前面的人所得的娃娃数加起来，娃娃数小于0的视为0
sum += ((max-i)>0?(max-i):0);
}
for(int j = n;j>k;j--){ //把排在他后面的人所得的娃娃数加起来，娃娃数小于0的视为0
sum += ((max-(j-k))>0?(max-(j-k)):0);
}
sum += max; //再加上他本人的娃娃数
if(sum<m){ //小于m说明还没达到最大极限值，继续循环
continue;
}else if(sum==m){ //max恰好是最佳合理分配
break;
}else{ //还没达到满足为max的所需最少娃娃总数的分配，将max-1即可
max--;
break;
}
}
return max;
}
}

发表于 2018-08-22 16:41:55 回复(0)

在午休的柯基很有礼貌

  importjava.util.Scanner; 
    
  publicclassMain { 
      publicstaticvoidmain(String[] args) { 
          Scanner in = newScanner(System.in); 
          intn = in.nextInt();//人数 
          intm = in.nextInt();//玩偶数 
          intk = in.nextInt();//位置 
          if(k==0||k>n) 
              System.out.print(0); 
          else{ 
              k=k-1; 
              int[] count=newint[n]; 
              for(inti=0;i<n;i++) { 
                  count[i]=0; 
              } 
              while(m!=0) { 
                  if((k<=0||count[k]==count[k-1])&&(k>=n-1||count[k]==count[k+1])) { 
                      count[k]=count[k]+1; 
                      m-=1; 
                  } 
                    
                  if(m!=0&&(k>0&&count[k]>count[k-1])) { 
                      dispatchLeft(count,k-1); 
                      m-=1; 
                  } 
                    
                  if(m!=0&&(k<n-1&&count[k]>count[k+1])) { 
                      dispatchRight(count,k+1); 
                      m-=1; 
                  } 
                    
                
              } 
              System.out.print(count[k]); 
          }   
      } 
      publicstaticvoiddispatchLeft(int[] c,intp) { 
          if(p==0||c[p-1]==c[p]) { 
              c[p]=c[p]+1; 
              return; 
          } 
          dispatchLeft(c,p-1); 
            
      } 
      publicstaticvoiddispatchRight(int[] c,intp) { 
          if(p==c.length-1||c[p+1]==c[p]) { 
              c[p]+=1; 
              return; 
          } 
          dispatchRight(c,p+1); 
      } 
  } 

发表于 2018-03-25 17:00:31 回复(1)

cainiao23333

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n, m, k;
	cin >> n >> m >> k;
	int p = 0;
	if (n == 0 || m == 0 || k <= 0 || k > n) {
		p = 0;
	}
	else {
		p = (n * n + 2 * k * k + 2 * m - 2 * k * n - k)/(2 * n);
		if ((p - k + 1) < 0) {
			p = n - k + 1;
		}
		else if ((p - n + k) < 0) {
			p = k;
		}
	}
	cout << (p <= m ? p : m) << endl;
	//system("pause");
	return 0;
}

发表于 2019-08-09 16:34:07 回复(0)

执伞的侍从

  importjava.util.*; 
  publicclassMain{ 
  publicstaticvoidmain(String[] args){ 
  Scanner input=newScanner(System.in); 
  String[] s=input.nextLine().split(" "); 
  int  num=Integer.parseInt(s[0]); 
  int  total=Integer.parseInt(s[1]); 
  int  k=Integer.parseInt(s[2]); 
  if(k==0||k>num)   System.out.println(0); 
  else{ 
  int  n=0; 
  int  left=k, right=k; 
  while(left>=1){ 
        n+=k-left; 
       left--; 
        } 
  while(right<=num){ 
          n+=num-right; 
          right++; 
            } 
  System.out.println((total+n)/num); 
       } 
  } 
  } 

编辑于 2018-05-08 16:51:20 回复(2)

C/C++

emptyCoder

#include <iostream>

using namespace std;

int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    if (n && (k>=1 && k<=n))
    {
        int s = ((n - k + 1)*(n - k) >> 1) + (k * (k - 1) >> 1); //*、+优先级大于>>
        for (int i = 0; i < n; i++)
        {
            if ((m + s - i) % n == 0)
            {
                cout << (m + s - i) / n << '\n';
                break;
            }
        }
    }
    else cout << "0" << '\n';
    return 0;
}

编辑于 2018-04-09 13:14:28 回复(2)

嗯了呗

  思想：把位置，数量，玩偶为0的特殊处理，直接输出0，剩余的情况k位置拥有n个玩偶赢的话，那么会变为一个数组：n-j(j位置的玩偶数).......n-1,n，n-1,n-2....j-k(位置j的玩偶数)，直接等差数列求和就可以了。 
  import java.util.Scanner; 
    
  publicclassMain { 
      publicstaticvoidmain(String[] args) { 
          Scanner sc = newScanner(System.in); 
          while(sc.hasNext()) { 
              int n = sc.nextInt(); 
              int m = sc.nextInt(); 
              int k = sc.nextInt(); 
              if(k == 0||n==0||m==0||k>n) { 
                  System.out.println(0); 
              } else{ 
                  int count1 = 0; 
                  int count2 = 0; 
                  int max = 0; 
                  for(inti = m; i >0; i--) { 
                      count1 = (n - k + 1) * i + ((n - k + 1) * (n - k) / 2) * (-1); 
                      count2 = k * i + (k * (k - 1) / 2) * (-1); 
                      if((count1 + count2 - i) <= m && i > max) { 
                          max = i; 
                      } 
                  } 
                  System.out.println(max); 
    
              } 
          } 
      } 
  } 