第一次作业

题解

【题目】[1]

A Design Tutorial: Learn from Math

题目大意：

    给定一个数n（12<=n<=10^6)，求出符合以下要求的x和y：
    1.x+y=n
    2.x和y都是合数

解题思路：

    显然，若n为偶数，可以表示为两个偶数相加；若n为奇数，可以表示为一个奇数加一个偶数。而大于2的所有偶数都是合数，最小的偶合数为4，最小的奇合数为9。所以大于等于12的偶数可以表示为4+（n-4），大于12的奇数可以表示为9+（n-9）。
    时间复杂度O(1)，空间复杂度O(1)。

AC代码：

#include <stdio.h>
int panduan(int x)
{
    for(int i=2;i*i<=x;i++)
        if(x%i==0)
        return 1;
    return 0;
}
int main()
{
    int n,i;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=4;i<=n/2;i++)
        {
            if(panduan(i)&&panduan(n-i))
            {
                printf("%d %d\n",i,n-i);
                break;
            }
        }
    }
    return 0;
}

【题目】【2】

**B - Design Tutorial: Learn from Life **

题目大意：

   有一个电梯，每一个人都想乘电梯到达自己想要到达的楼层！从a层到b层的时间是|a-b|，乘客上下电梯的时间忽略不计，问至少需要多少时间？

解题思路：

  这个使用的是贪心的思想，首先对所有人要到的楼层进行一次从大到小排序，然后开始吧n%k个人放到他们要到的楼层。然后将k-(n%k)个人带到啊【n%k】层，然后再下来接人，重复此操作，然后将所有人都送到他们想到的楼层。

AC代码：

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int a[2008];
int main()
{
    int n,i,k;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        int sum=0;
        for(i=n-1;i>=0;i-=k)
        {
            sum+=2*(a[i]-1);
        }
        printf("%d\n",sum);
    }
    return 0;
}