首页 > 试题广场 >

小易的考试成绩

[编程题]小易的考试成绩
  • 热度指数:1232 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

小易参加了一次考试,这场包含 n 个题目,第 i 个题目的分数是 si 。

如果小易第 i 题目回答正确,他将得到 Si 分,否则该题目他将得到 0 分。

最终的考试得分是所有题目得分的总和。

由于阅卷老师很讨厌数字 5,在阅卷时如果一个学生的考试总分中含有数字 5,那么阅卷老师将气愤地给他 0 分。

那么小易考试的最高得分是多少?


输入描述:
输入的第一行是正整数 n(1<=n<=100)  ,代表这场考试的题目数。
接下一行含有n个正整数 s1,s2,s3....s(1<= si <=200)


输出描述:
输出一个整数,代表小易考试的最高得分。
示例1

输入

5
5 15 5 15 5

输出

40

说明

如果所有题目都答对,总分为45,但里面包含了数字5,所以最高得分应该为40
示例2

输入

5
5 15 5 15 8

输出

48
示例3

输入

1
5

输出

0
package niuke.wangyi_2021;

import java.util.Scanner;

public class Main_2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] res = new int[n];
        for(int i = 0 ; i < n ; i++)
        {
            res[i] = scanner.nextInt();
        }
        new Main_2().search(res);
    }
    private void search(int[] res )
    {
        int max1 = 0;
        for(int i = 0 ; i < res.length ; i++)
        {
            max1 += res[i];
        }
        if(pan(max1))
        {
            System.out.println(max1);
            return;
        }
        boolean[] result = new boolean[max1 + 1];
        result[0] = true;
        for(int i = 0 ; i < res.length ; i++ )
        {

            for(int j = max1 ; j >= res[i] ; j--)
            {
                if(result[j])
                    continue;
                if(result[j - res[i]]){
                    result[j] = true;
                }
            }
        }
        for(int i = max1 ; i >= 0; i--)
        {
            if(result[i] && pan(i))
            {
                System.out.print(i);
                return;
            }
        }
    }
    private boolean pan(int n)
    {
        if(String.valueOf(n).contains("5"))
            return false;
        return true;
    }
}

发表于 2022-07-05 11:05:33 回复(0)
先用动规求解背包问题,得到所有能取到的分数,然后再按降序检验分数,第一个不包含5的分数即为所求
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        int[] scores = new int[n];
        int sum = 0;
        for(int i = 0; i < n; i++){
            scores[i] = Integer.parseInt(strArr[i]);
            sum += scores[i];
        }
        int[] dp = new int[20001];    // 1~100个1~200的数总和最大为20000
        // 求解背包问题
        dp[0] = 1;
        dp[sum] = 1;
        for(int i = 0; i < n; i++){
            dp[scores[i]] = 1;
            for(int j = 0; j <= sum; j++){
                if(dp[j] == 1 && j - scores[i] >= 0)
                    dp[j - scores[i]] = 1;
            }
        }
        // 降序依次检测分数是否符合不含5
        for(int score = sum; score >= 0; score--){
            if(dp[score] == 1 && !String.valueOf(score).contains("5")){
                System.out.println(score);
                break;
            }
        }
    }
}


编辑于 2021-01-18 11:42:10 回复(4)

首先考虑这个问题

我有n个礼物,价值分别为,我可以选其中0个或者多个,并把它们的价值相加,得到sum,我想知道sum有多少种可能的取值?比如[1,1,1]三个礼物,sum有0,1,2,3四种取值。

dp[i]=1是存在可能的选择方法,使得总和为i。

怎么理解呢?

dp[0]代表空集合,每次取一个score,加入所有集合中,更新!

为了不让同一个礼物反复更新,从后往前,比如[3, .....]这个礼物列表,如果从前往后,j=3时dp[3]=1,j=6时候发现dp[3]是1,那dp[6]也是1,相当于3+3,3用了2次,哒咩!

时间复杂度

复杂度海⭐️

vector<int> possibleSums(const vector<int>& score) {
    int sum = 0;
    for (auto n : score)
        sum += n;
    vector<int> dp(sum + 1);
    dp[0] = 1;
    for (int sco : score) {
        for (int j = sum; j >= sco; --j) {
            if (dp[j - sco]) {
                dp[j] = 1;
            }
        }
    }
    return dp;
}

具体到这一题就是算出所有的取值,然后从后往前检查是否包含5,输出第一个不包含5的分数!
完整代码

#include<bits/stdc++.h>
using namespace std;

int maxScore(const vector<int>& score) {
    int sum = 0;
    for (auto n : score)
        sum += n;
    vector<int> dp(sum + 1);
    dp[0] = 1;
    for (int sco : score) {
        for (int j = sum; j >= sco; --j) {
            if (dp[j - sco]) {
                dp[j] = 1;
            }
        }
    }
    auto have5 = [](int n) {
        while (n) {
            int m = n % 10;
            n /= 10;
            if (m == 5)
                return true;
        }
        return false;
    };
    for (int i = sum; i >= 0; --i) {
        if (dp[i] &&  !have5(i)) return i;
    }
    return -1;
}

int main() {
    int n;
    cin >> n;
    vector<int> score(n);
    for (int i = 0; i < n; i++)
        cin >> score[i];
    cout << maxScore(score);
}
发表于 2023-08-26 22:15:34 回复(0)
//C++背包 如果一开始发现和没有5,直接返回即可
#include <vector>
#include <iostream>
using namespace std;
bool havefive(int sum)
{
    while(sum)
    {
        if(sum%10==5)
            return true;
        sum/=10;
    }
    return false;
}
int main()
{
    int n;
    cin>>n;
    vector<int> v(n);
    int sum=0;
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
        sum+=v[i];
    }
    if(!havefive(sum))
        {
        cout<<sum<<endl;
        return 0;
        }
    vector<bool> dp(sum+1);
    dp[0]=true;
    int maxadd=0;
    for(auto e:v)
    {
        maxadd+=e;
        for(int i=maxadd;i>=e;i--)
        {
            if(dp[i-e]==true)
                dp[i]=true;
        }
    }
    for(int i=sum;i>=0;i--)
    {
        if(dp[i]==true&&(!havefive(i)))
        {
            cout<<i<<endl;
            break;
        }
    }
    return 0;
}

发表于 2022-08-11 16:59:52 回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        ArrayList<Integer> scores = new ArrayList<>();
        String[] s = br.readLine().split(" ");
        for(int i=0;i<n;i++){
            scores.add(Integer.parseInt(s[i]));
        }

        // 将所有题目分数从大到小排列
        scores.sort(Collections.reverseOrder());
        // 先对所有分数求和
        int sum = scores.stream().mapToInt(Integer::intValue).sum();

        // 如果天然的总分有数字5存在
        if(String.valueOf(sum).contains("5") && scores != null){
            int tempSum = -1;
            // 逐一尝试总分减去一题分数是不是就不含5了,如果是记录临时总分
            // 因为题目分数从大到小排列 经过一轮遍历,可以找到让现在的总分不含5的最大情况
            for(int i: scores){
                if(!String.valueOf(sum - i).contains("5")){
                    tempSum = Math.max(tempSum, sum - i);
                }
            }
            
            // 如果确实可以靠减掉一题分数符合题目要求,说明找到了直接输出结束程序
            if(tempSum != -1){
                System.out.println(tempSum);
                return;
            }else {  // 如果没有找到减掉一题符合要求的结果,就减掉分值最低的一题
                sum -= scores.get(scores.size() - 1);
                scores.remove(scores.size() - 1);
            }

        }
        System.out.println(sum);
    }

}

发表于 2022-03-25 20:16:32 回复(0)
这里递归的写法导致程序执行时会尽量尝试不放弃题目,或者优先放弃分数较少的题目,那第一次得到不包含5的分数就是最终答案。
在一定程度上能够对原始递归优化。
#include <iostream>
#include <algorithm>
using namespace std;
int n,*arr;
int result;
int now;
bool IfNo5(){
    string str=to_string(now);
    int len=str.length();
    for(int i=0;i<len;++i)
        if(str[i]=='5')
            return 0;
    return 1;
}
void dfs(int index){
    if(result)
        return;
    if(IfNo5()){
        result=now;
        return;
    }
    if(index){
        if(!result)
            dfs(index-1);
        if(!result){
            now-=arr[index];
            dfs(index-1);
            now+=arr[index];
        }
    }
    else{
        now-=arr[index];
        if(IfNo5())
            result=now;
        now+=arr[index];
    }
}
int main(){
    cin>>n;
    arr=new int[n];
    for(int i=0;i<n;++i){
        cin>>arr[i];
        now+=arr[i];
    }
    if(!IfNo5()){
        sort(arr,arr+n);
        dfs(n-1);
    }
    else
        result=now;
    cout<<result<<endl;
    delete[]arr;
    return 0;
}


编辑于 2022-01-02 22:41:28 回复(0)
n=int(input())
s=list(map(int,input().split()))
res=0
def dfs(s,index,total):
    global res
    if index>=len(s):
        if '5' not in str(total):
            res=max(res,total)
        return
    dfs(s,index+1,total+s[index])
    dfs(s,index+1,total)
dfs(s,0,0)
print(res)

递归超时,咋整
发表于 2021-09-18 13:40:52 回复(0)
import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] secLine = br.readLine().trim().split(" ");
        int[] pts = new int[n];
        int sum = 0;
        for(int i = 0; i < n; i++){
            pts[i] = Integer.parseInt(secLine[i]);
            sum += pts[i];
        }
        Arrays.sort(pts);
        // 创建一个divide用于检测有没有5
        if(!has5(sum)){
            System.out.print(sum);
        }else{
            for(int i = 0; i < n; i++) {
                if(!has5(sum - pts[i])){
                    System.out.print(sum - pts[i]);
                    break;
                }
            }
        }

    }
    private static boolean has5(int num){
        boolean has = false;
        int divide = num;
        while(divide != 0){
            int single = divide % 10;
            if(single == 5){
                has = true;
                break;
            }
            divide /= 10;
        }
        return has;        
    }
}
发表于 2021-08-20 19:25:23 回复(1)
n=int(input().strip())
A=list(map(int,input().strip().split()))
A=sorted(A)                   #升序排序
SsumA='%d' % sum(A)
while SsumA.count('5')!=0:    #和值有5,处理
    flag=0
    for i in range (len(A)):
        tmp=A[i]
        sumA=sum(A)-tmp
        SsumA='%d' % sumA
        if SsumA[-1]!='5':
            del A[i]
            flag=1
            break
    if flag==0:
        del A[i]
        SsumA='%d' % sum(A)
print(sum(A))

编辑于 2021-05-19 09:15:02 回复(1)