ccf201612题解

ccf题解 题解

---

1.201612-01 中位数

题目描述

试题编号： 201612-1
试题名称： 中间数
时间限制： 1.0s
内存限制： 256.0MB

解析

题目中规定的中位数：一个数小于它的数的个数等于大于它的数的个数。
因为题目规模较小，所以我们可以采用$O(n^2)$的算法。
即选中一个数，然后遍历整个数组分别找到比它小的数的个数和比它大的数的个数。

通过代码

//2148609   <13100928923>   <王恪楠>   中间数 11-07 12:02 610B    C++ 正确  100 46ms    2.535MB
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1050];
int main()
{
    int flag = 1;       //标记，是否找到了中位数。如果flag值不变，则输出-1. 
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
        scanf("%d", &a[i]);
    for(int i = 1; i <= n; i ++){
        int cnt0 = 0, cnt1 = 0;             //cnt0比a[i]小的数的个数，cnt1比a[i]大的数的个数.
        for(int j = 1; j <= n; j ++){
            if(a[i] > a[j])
                cnt1 ++;
            if(a[i] < a[j])
                cnt0 ++;
        }
        if(cnt0 == cnt1){
            printf("%d", a[i]);
            flag = 0;
            break;
        }
    }
    if(flag == 1)
        printf("-1");
    return 0;
}

2.201612-02 工资计算

题目描述

试题编号： 201612-2
试题名称： 工资计算
时间限制： 1.0s
内存限制： 256.0MB

解析

题意不难理解，需要把握准确。

设$S$为税前工资。
对于超出3500元的部分X实行阶梯缴税，

$$X = S - 3500$$

计算出需要缴纳的税款$tax$，$S - tax$即是税后工资。
当$S - tax == T$时，$S$即是所求。

因为所求$S$一定是$100$的倍数，所以枚举$100 \sim 10000000$全部的$100$倍数。

通过代码

2148234 <13100928923>   <王恪楠>   工资计算    11-06 22:16 818B    C++ 正确  100 31ms    2.535MB
#include <bits/stdc++.h>
using namespace std;
int cal(int x)
{
    int sum = x, tax = 0;;
    if(x < 3500)
        return x;
    x -= 3500;
    if(x > 80000)    //阶梯缴税. 
        tax += (x - 80000) / 100 * 45, x = 80000;
    if(x > 55000)
        tax += (x - 55000) / 100 * 35, x = 55000;
    if(x > 35000)
        tax += (x - 35000) / 100 * 30, x = 35000;
    if(x > 9000)
        tax += (x - 9000) / 100 * 25, x = 9000;
    if(x > 4500)
        tax += (x - 4500) / 100 * 20, x = 4500;
    if(x > 1500)
        tax += (x - 1500) / 100 * 10, x = 1500;
    tax += x / 100 * 3;
    return sum - tax;
}
int main()
{
    int t;
    scanf("%d", &t);
    for(int i = 1; i <= 100000; i ++)      //枚举. 
    if(cal(100 * i) == t){
            printf("%d", i * 100);
            break;
    }
    return 0;
}