首页 > 试题广场 >

串珠子

[编程题]串珠子

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

现在A和B在玩一个游戏，这个游戏首先给了他们很多珠子，珠子有两种颜色，一种蓝色，一种黄色，我们假定两种珠子都有无限多。A需要选择n颗珠子(n为奇数)，然后由B串成一串项链(顺序由B确定,这里的项链也就是一个环)。假如在最后串成的项链中，A能够找到两个不同位置的蓝色珠子，并在这两处把这个项链断开成两段，其中一段恰好长度为(n+1)/2那么A就胜利了，注意这里为整数截断除法且这个长度是不包括选出的两颗珠子的。现在请你计算出A至少要选择多少颗蓝色珠子，才能保证无论B怎么串，他都能获胜。举个例子，当A选了7颗珠子，其中有3颗蓝珠子，那么如果B串的项链为"蓝蓝红红红红蓝"，则A能获胜，若B串的项链为"蓝蓝红红蓝红红"，则A不能获胜。

输入描述:

给定一个整数n，为A要选出的珠子颗数.

输出描述:

请返回A至少要选的蓝珠子颗数。

示例1

输入

输出

算法知识视频讲解

Alex-大伟

import java.util.*;

public class Chain {
    public int findK(int n) {
        // write code here
        if(n % 3 == 0){
            return n / 2;
        }
        else{
            return n / 2 + 1 ;
        }
    }
}

发表于 2016-09-29 11:24:08 回复(0)

静牛


	import java.util.*;



	public class Chain {



	    public int findK(int n) {



	            return n/2+((n%3)>0?1:0);



	    }



	}

编辑于 2016-09-09 15:52:31 回复(0)

KULA

  classChain { 

  public: 

      intfindK(intn) { 

          if(n%3==0) 

              n=(n-1)/2; 

          elsen=(n+1)/2; 

          returnn; 

      } 

  };

发表于 2016-04-20 15:24:23 回复(13)

loolroco

http://www.voidcn.com/blog/u012742806/article/p-5803395.html

发表于 2016-08-09 11:16:09 回复(1)

lqqqdu

//不明白为什么，反正看别人这样写了就抄了

	 if(n %3==0){



	            returnn /2;



	        }



	        else{



	            returnn /2+1;



	        }

发表于 2017-12-23 18:26:03 回复(0)

C/C++

YoHoooo

我会告诉你们我用了深搜，然后超时。
然后利用深搜纪录了一些答案，最后找规律么？
别问我为什么，反正答案对了。。。

classChain {   
    public:   
    intfindK(intn) {
    intp=(n+1)/6;   
    if(n%6==5)return(n-1)/2+1;   
    else return p*3+1;   
    }   
    };

编辑于 2017-02-14 16:05:13 回复(0)

C/C++

半道迴歸

class Chain {
public:
    int findK(int n) {
        // write code here
        //神棍的答案，没法证明，貌似从对手的最优策略考虑
        if(n%3==0){
         return (n-1)/2;
        }
        else{
            return (n+1)/2;
        }
    }
};

发表于 2016-12-16 11:20:43 回复(0)

上下求索

import java.util.*;
public class Chain {
    public int findK(int n) {
        // write code here
		return n % 3 == 0 ? (n - 1) / 2 : (n + 1) / 2;
    }
}

发表于 2016-10-30 18:51:34 回复(0)

lizhenfeng

一句话说不清，不说了

发表于 2016-08-10 16:28:29 回复(0)

枫叶123465


	importjava.util.*;



	 



	publicclassChain {



	    publicintfindK(intn) {



	        // write code here



	        if(n%3==0){



	            return(n-1)/2;



	        }



	        else{



	            returnn-(n-1)/2;



	        }



	    }



	}