首页 > 其他分享 >HDU 1029 Ignatius and the Princess IV(基础dp)

HDU 1029 Ignatius and the Princess IV(基础dp)

时间:2023-05-26 15:07:20浏览次数:38  
标签:HDU int scanf ans 1029 Ignatius ++ cnt include


传送门

题目大意就是给你n个数(保证n为一个奇数),存在一个数出现的次数大于(n+1)/2次,求这个数;

这个数出现的次数比其他数出现的次数加起来还多,那么当这个数出现时+1,其他的数出现时-1,最后得到的数为正数。

假定一个数为特殊数,若当前数与特殊数相同则cnt++,若不相同则cnt--,如果这时cnt<0,用当前数替代特殊的数。不管怎么样,由于特殊数次数大于(n+1)/2次,最终保留的数一定是特殊数。
代码如下

#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define inf 0x3f3f3f3f
using namespace std;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int ans,x,cnt = 0;
        for(int i = 0;i < n; i++)
        {
            scanf("%d",&x);
            if(ans == x)
                ++cnt;
            else
                --cnt;
            if(cnt < 0)
            {
                cnt = 0;
                ans = x;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

我还写了一个比较暴力的,居然过了,应该是他们评测的数据有问题,没有太大的数,也一并把代码贴在这里,推荐大家看上面的思路,下面这个的思路我就不说了,大家一看就明白了。

#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define inf 0x3f3f3f3f
using namespace std;
int main()
{
    int n,a[1000000];
    while(~scanf("%d",&n))
    {
        memset(a,0,sizeof(a));
        for(int i = 0;i < n; i++)
        {
            int x;
            scanf("%d",&x);
            a[x]++;
        }
        int maxn = 0,index;
        for(int i = 0;i < 1000000; i++)
        {
            if(maxn < a[i])
            {
                maxn = a[i];
                index = i;
            }
        }
        printf("%d\n",index);
    }
    return 0;
}

 

标签:HDU,int,scanf,ans,1029,Ignatius,++,cnt,include
From: https://blog.51cto.com/u_16131191/6356098

相关文章

  • HDU 2084 数塔(动态规划入门)
    传送门中文题就不给大家翻译了(手动滑稽),反正大家都看得懂。这是一道动态规划入门的题目,只需要找出状态转移方程即可。状态方程:dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j])(dp[i][j]表示从第i层第j个数开始搜能得到的最大数)代码如下:#include<cstring>#include<iostream>#include<......
  • HDU 1024 Max Sum Plus Plus(动态规划)
    传送门题意是给你个数字序列,现在让你把这个序列分成m个连续的子序列,且要求这m个子序列的累加和最大。思路:这道题的题意可以理解为问在序列为末尾时,把序列分为m个子序列这个状态时的最大累加和,那么可以得出这个状态应该是由上一个状态转移得来:(因为dp[i][j]表示数到第j个字符时,前j个......
  • hdu 4758 Walk Through Squares(AC自动机+DP,4级)
    WalkThroughSquaresTimeLimit:4000/2000MS(Java/Others)    MemoryLimit:65535/65535K(Java/Others)TotalSubmission(s):234    AcceptedSubmission(s):58ProblemDescription  Onthebeamingdayof60thanniversaryofNJUST,asamilitary......
  • HDU-1003- Max Sum (动态规划)
    MaxSumTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):192050    AcceptedSubmission(s):44727ProblemDescriptionGivenasequencea[1],a[2],a[3]......a[n],yourjobistocalculatethe......
  • hdu-2680-Choose the best route(dijkstra)
    ChoosethebestrouteTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):10470    AcceptedSubmission(s):3367ProblemDescriptionOneday,Kikiwantstovisitoneofherfriends.Assheis......
  • hdu-1869-六度分离(dijkstra)
    六度分离TimeLimit:5000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):5935    AcceptedSubmission(s):2395ProblemDescription1967年,美国著名的社会学家斯坦利·米尔格兰姆提出了一个名为“小世界现象(small......
  • hdu:gcd(欧拉函数)
    ProblemDescriptionThegreatestcommondivisorGCD(a,b)oftwopositiveintegersaandb,sometimeswritten(a,b),isthelargestdivisorcommontoaandb,Forexample,(1,2)=1,(12,18)=6.(a,b)canbeeasilyfoundbytheEuclideanalgorithm.NowCarpiscon......
  • hdu:LCIS(线段树+区间合并)
    ProblemDescriptionGivennintegers.Youhavetwooperations:UAB:replacetheAthnumberbyB.(indexcountingfrom0)QAB:outputthelengthofthelongestconsecutiveincreasingsubsequence(LCIS)in[a,b].InputTinthefirstline,indicatingt......
  • hdu:这是真正的水题(RMQ)
    ProblemDescription在缺水的地方,水是非常有限的资源,所以人们常常为争夺最大的水源而战。给定一系列水源,用a1,a2,a3,…,an代表水源的大小。给定一组查询,每个查询包含2整数L和R,请找出L和R之间最大的水源。Input输入数据首先给定一个整数T(T≤10)表示测试用例的数量。......
  • hdu:Party(2-SAT)
    ProblemDescription有n对夫妻被邀请参加一个聚会,因为场地的问题,每对夫妻中只有1人可以列席。在2n个人中,某些人之间有着很大的矛盾(当然夫妻之间是没有矛盾的),有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n个人同时列席?Inputn:表示有n对夫妻被邀请(n<=1000)m:表......