Codeforces MemSQL.Round.1

题目大意：

　　有1e6个人，序号从1到1e6，现在要邀请前25个人组成队伍，但是被选中的人可能会推掉邀请，如果有人没去，就要从第26个人开始按序号补满25个队员。你现在已知有K个人的序号，求出最少有多少个人推掉了邀请。

　　输入一行一个整数：代表已知的K个人（最多25人）。

　　输入一行K 个整数：代表已知K个人的序号。

　　输出一行一个整数：代表最少有多少人推掉了邀请。

　　样例输入：25

　　　　　　　2 3 4 5 6 7 8 9 10 11 12 14 15 16 17 18 19 20 21 22 23 24 25 26 28

　　　　　　　5

　　　　　　　16 23 8 15 4

　　　　　　　3

　　　　　　　14 15 92

　　样例输出：3　　

　　　　　　　0　　

　　　　　　　67

解题思路：

　　此题题干较为不好理解，但是思路很简单：sort后看最大数。

　　如果大于25，结果就是最大数和25的差。

　　小于等于25，结果均为0。

A C 代码：

<span style="color: #008080"> 1</span> <span style="color: #0000ff">import</span> java.util.*<span style="color: #000000">;
</span><span style="color: #008080"> 2</span> 
<span style="color: #008080"> 3</span> <span style="color: #0000ff">public</span> <span style="color: #0000ff">class</span><span style="color: #000000"> Main{
</span><span style="color: #008080"> 4</span>     <span style="color: #0000ff">public</span> <span style="color: #0000ff">static</span> <span style="color: #0000ff">void</span><span style="color: #000000"> main(String[] args){
</span><span style="color: #008080"> 5</span>         Scanner sc = <span style="color: #0000ff">new</span><span style="color: #000000"> Scanner(System.in);
</span><span style="color: #008080"> 6</span>         <span style="color: #0000ff">while</span><span style="color: #000000">(sc.hasNext()){
</span><span style="color: #008080"> 7</span>             <span style="color: #0000ff">int</span> n =<span style="color: #000000"> sc.nextInt();
</span><span style="color: #008080"> 8</span>             <span style="color: #0000ff">int</span> m[] = <span style="color: #0000ff">new</span> <span style="color: #0000ff">int</span><span style="color: #000000">[n];
</span><span style="color: #008080"> 9</span>             <span style="color: #0000ff">for</span>(<span style="color: #0000ff">int</span> i = 0;i < n;i ++<span style="color: #000000">){
</span><span style="color: #008080">10</span>                 m[i] =<span style="color: #000000"> sc.nextInt();
</span><span style="color: #008080">11</span> <span style="color: #000000">            }
</span><span style="color: #008080">12</span> <span style="color: #000000">            Arrays.sort(m);
</span><span style="color: #008080">13</span>             <span style="color: #0000ff">if</span>(m[n - 1] > 25){System.out.println(m[n - 1] - 25<span style="color: #000000">);}
</span><span style="color: #008080">14</span>             <span style="color: #0000ff">else</span>{System.out.println("0"<span style="color: #000000">);}
</span><span style="color: #008080">15</span> <span style="color: #000000">        }
</span><span style="color: #008080">16</span> <span style="color: #000000">    }
</span><span style="color: #008080">17</span> }

B - Lazy Security Guard

题目大意：

　　求解n个边长为单位长度的正方形拼成的图形的最短周长。

　　输入一行一个整数：n，代表给你n个小正方形。

　　输出一行一个整数：代表得出的最小周长。

解题思路：

　　一个简单的公式，2 * ((ceil)(2 * sqrt(n)))。

　　或者，(ceil)(4 * sqrt(n)) 然后判断，奇数加一，偶数不变。

A C 代码：

<span style="color: #008080"> 1</span> <span style="color: #0000ff">import</span> java.util.*<span style="color: #000000">;
</span><span style="color: #008080"> 2</span> 
<span style="color: #008080"> 3</span> <span style="color: #0000ff">public</span> <span style="color: #0000ff">class</span><span style="color: #000000"> Main{
</span><span style="color: #008080"> 4</span>     <span style="color: #0000ff">public</span> <span style="color: #0000ff">static</span> <span style="color: #0000ff">void</span><span style="color: #000000"> main(String[] args){
</span><span style="color: #008080"> 5</span>         Scanner sc = <span style="color: #0000ff">new</span><span style="color: #000000"> Scanner(System.in);
</span><span style="color: #008080"> 6</span>         <span style="color: #0000ff">while</span><span style="color: #000000">(sc.hasNext()){
</span><span style="color: #008080"> 7</span>             <span style="color: #0000ff">int</span> n =<span style="color: #000000"> sc.nextInt();
</span><span style="color: #008080"> 8</span>             <span style="color: #0000ff">double</span> p = 2 *<span style="color: #000000"> Math.sqrt(n);
</span><span style="color: #008080"> 9</span>             <span style="color: #0000ff">int</span> pp = (<span style="color: #0000ff">int</span><span style="color: #000000">)Math.ceil(p);
</span><span style="color: #008080">10</span>             System.out.println(2 *<span style="color: #000000"> pp);
</span><span style="color: #008080">11</span> <span style="color: #000000">        }
</span><span style="color: #008080">12</span> <span style="color: #000000">    }
</span><span style="color: #008080">13</span> }

　　C - Pie Rules

题目大意：

　　两个人（A和B）按照以下规则分n堆糖，两个人都按照最优策略。

　　从B开始，如果B拿走当前堆的糖，那么下一堆轮到A选择要不要。

　　如果B不要这堆糖，那么就将这堆糖给A，自己继续选择下一堆要不要。

　　直到所有的糖都分完。求解两人各获得多少糖。

　　输入一行一个整数：N，代表N堆糖果（N ∈ [1,50]）。

　　输出一行N 个整数：每个整数代表一堆糖的数量。从头到尾按顺序分糖。

　　输出一行两个整数：分别代表A和B获得了多少糖。

　　样例输入：3　　　　　　　　　5

　　　　　　　141 592 653　　　　10 21 10 21 10

　　样例输出：653 733　　　　　　31 41

解题思路：

　　一道DP题目。dp[i]代表分到当前堆时，当前持有分配权的人最多能得到多少苹果。sum[i]代表当前堆时一共分配了多少苹果。

　　最开始一直正向分配，始终出现错误。。。

　　然后才知道应该反向去分配。。。

　　因为正向分配的时候，并不知道谁持有分配权。

A C 代码：

<span style="color: #008080"> 1</span> <span style="color: #0000ff">import</span> java.util.*<span style="color: #000000">;
</span><span style="color: #008080"> 2</span> 
<span style="color: #008080"> 3</span> <span style="color: #0000ff">public</span> <span style="color: #0000ff">class</span><span style="color: #000000"> Main{
</span><span style="color: #008080"> 4</span>     <span style="color: #0000ff">public</span> <span style="color: #0000ff">static</span> <span style="color: #0000ff">void</span><span style="color: #000000"> main(String[] args){
</span><span style="color: #008080"> 5</span>         Scanner sc = <span style="color: #0000ff">new</span><span style="color: #000000"> Scanner(System.in);
</span><span style="color: #008080"> 6</span>         <span style="color: #0000ff">while</span><span style="color: #000000">(sc.hasNext()){
</span><span style="color: #008080"> 7</span>             <span style="color: #0000ff">int</span> n =<span style="color: #000000"> sc.nextInt();
</span><span style="color: #008080"> 8</span>             <span style="color: #0000ff">int</span> pie[] = <span style="color: #0000ff">new</span> <span style="color: #0000ff">int</span>[n + 1<span style="color: #000000">];
</span><span style="color: #008080"> 9</span>             <span style="color: #0000ff">int</span> dp[] = <span style="color: #0000ff">new</span> <span style="color: #0000ff">int</span>[n + 1<span style="color: #000000">];
</span><span style="color: #008080">10</span>             <span style="color: #0000ff">int</span> sum[] = <span style="color: #0000ff">new</span> <span style="color: #0000ff">int</span>[n + 1<span style="color: #000000">];
</span><span style="color: #008080">11</span>             <span style="color: #0000ff">for</span>(<span style="color: #0000ff">int</span> i = n;i >= 1;i --<span style="color: #000000">){
</span><span style="color: #008080">12</span>                 pie[i] =<span style="color: #000000"> sc.nextInt();
</span><span style="color: #008080">13</span> <span style="color: #000000">            }
</span><span style="color: #008080">14</span>             <span style="color: #0000ff">for</span>(<span style="color: #0000ff">int</span> i = 1;i <= n;i ++<span style="color: #000000">){
</span><span style="color: #008080">15</span>                 sum[i] = sum[i - 1] +<span style="color: #000000"> pie[i];
</span><span style="color: #008080">16</span> <span style="color: #000000">            }
</span><span style="color: #008080">17</span>             <span style="color: #008000">/*</span>
<span style="color: #008080">18</span> <span style="color: #008000">            System.out.print("sum[] = ");
</span><span style="color: #008080">19</span> <span style="color: #008000">            for(int i = 1;i <= n;i ++){
</span><span style="color: #008080">20</span> <span style="color: #008000">                System.out.print(sum[i] + " ");
</span><span style="color: #008080">21</span> <span style="color: #008000">            }System.out.println();
</span><span style="color: #008080">22</span>             <span style="color: #008000">*/</span>
<span style="color: #008080">23</span>             <span style="color: #0000ff">for</span>(<span style="color: #0000ff">int</span> i = 1;i <= n;i ++<span style="color: #000000">){
</span><span style="color: #008080">24</span>                 dp[i] = Math.max(dp[i - 1],sum[i] - dp[i - 1<span style="color: #000000">]);
</span><span style="color: #008080">25</span> <span style="color: #000000">            }
</span><span style="color: #008080">26</span>             <span style="color: #008000">/*</span>
<span style="color: #008080">27</span> <span style="color: #008000">            System.out.print("dp[] = ");
</span><span style="color: #008080">28</span> <span style="color: #008000">            for(int i = 1;i <= n;i ++){
</span><span style="color: #008080">29</span> <span style="color: #008000">                System.out.print(dp[i] + " ");
</span><span style="color: #008080">30</span> <span style="color: #008000">            }System.out.println();
</span><span style="color: #008080">31</span>             <span style="color: #008000">*/</span>
<span style="color: #008080">32</span>             System.out.println((sum[n] - dp[n]) + " " +<span style="color: #000000"> dp[n]);
</span><span style="color: #008080">33</span> <span style="color: #000000">        }
</span><span style="color: #008080">34</span> <span style="color: #000000">    }
</span><span style="color: #008080">35</span> }

Codeforces MemSQL.Round.1

标签：int()   nbsp   text   int   double   []   for   大数   one