pat乙级1060爱丁顿数

Question

pat乙级1060爱丁顿数

#include<bits/stdc++.h>
#define ll long long
int main( )
{
    ll n,result,max=-1;
    scanf("%lld",&n);
    ll input[n];
    for(ll i=0;i<n;i++)
    {
        scanf("%lld",&input[i]);
        max=input[i]>max?input[i]:max;
    }
    ll hash[max+1],dp[max+1];
    for(ll i=0;i<=max;i++) hash[i]=0;
    for(ll i=0;i<n;i++) hash[input[i]]++;
    dp[max]=hash[max];
    //if(dp[max]>=max&&max<=n) {printf("%lld",max);return 0;}
    for(ll i=max-1;1;i--)
    {
        if(i<=0) {result=0;break;}
        dp[i]=hash[i]+dp[i+1];
        if(dp[i]>=i&&i<=n) {result=i;break;}
        else if(dp[i]>=i) {result=n;break;}
    }
    printf("%lld",result);
    return 0;
}

里面我注释的那句话,如果不加就错1个测试用例,如果加了就错4个测试用例.

我的想法是建立一个hash表hash[i]用来存放骑行i公里的天数
再用建立一个dp表,dp[i]表示骑行公里大于等于i的天数
这样很轻松就能得到dp[i]=hash[i]+dp[i+1]
只要i从大到小遍历,找到第一个dp[i]>=i即可找到答案

我写完之后怎么试都是对的,但pta里面的测试用例就总是会错那么几个.有能帮帮我吗

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

从你给出的代码和描述来看，你已经很好地实现了乙级PAT（Programmable Area Tracking）的爱丁顿数问题的解题思路。你已经正确地建立了哈希表和动态规划数组，并且逻辑看起来也是正确的。但是在实际测试时出现问题，可能是因为你的代码在某些边界情况的处理上存在缺陷。这可能是因为以下原因：

1. 你的代码在计算过程中可能会忽略掉输入的第一个数或者第一个哈希表的初始值。你在循环中为数组input和hash分配空间时没有从索引0开始初始化。在某些系统中，默认创建的全零初始化可能导致不正确的行为。尤其是如果你首先获取了一个非常小的值，并且在第一个索引上的哈希值没有初始化，那么它可能是一个潜在的问题源。
2. 在动态规划的过程中，你可能没有正确处理当dp[i]等于某个值时的逻辑判断。在你的代码中，你试图在每次循环中更新result的值，但在某些情况下可能没有得到正确的结果。你应该确保你的逻辑判断是准确的，并且符合题目的要求。你应该检查所有可能的边界情况，以确保你的代码在所有情况下都能正确运行。

为了解决这个问题，我建议你检查以下几点：

• 确保你的输入和输出是正确的，并且与题目要求的格式一致。检查你的测试用例是否与题目提供的样本输出相匹配。
• 检查你的边界条件处理是否正确。特别是在循环中，你应该确保正确地处理了数组的起始和结束索引。尝试测试不同的测试用例，尤其是边界情况和特殊情况的测试用例。这可能有助于发现可能的错误源。同时检查动态规划方程的逻辑是否在所有情况下都是正确的。你应该测试那些可以使方程不成立的测试用例，看看它们是否会导致错误的结果。如果可能的话，尝试手动计算一些测试用例的结果，以确保你的代码是正确的。最后检查哈希表的初始化和更新是否正确无误。