九度OJ 1371(排序) 1372(DP) 1373(统计) 1374(统计) 1375(统计)

2024-04-02 01:58

本文主要是介绍九度OJ 1371(排序) 1372(DP) 1373(统计) 1374(统计) 1375(统计),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


1371:最小的K个数

http://ac.jobdu.com/problem.php?pid=1371

题意

输入n个整数,找出其中最小的K个数。

思路

排序然后输出。

代码

#include<stdio.h>
#include<algorithm>
#define N 200005
using namespace std;
int main()
{
        int n,k;
        int i;
        int a[N];
        while(scanf("%d%d",&n,&k)!=EOF)
        {
                for(i=0;i<n;i++)
                {
                        scanf("%d",&a[i]);
                }
                sort(a,a+n);
                for(i=0;i<k-1;i++)
                {
                        printf("%d ",a[i]);
                }
                printf("%d\n",a[k-1]);
        }
        return 0;
}
/**************************************************************
    Problem: 1371
    User: liangrx06
    Language: C++
    Result: Accepted
    Time:860 ms
    Memory:1728 kb
****************************************************************/

1372:最大子向量和

http://ac.jobdu.com/problem.php?pid=1372

题意

求向量中连续子向量的最大和,同时求出该子向量的第一个元素的下标和最后一个元素的下标。若是存在多个子向量,则输出起始元素下标最小的那个。

思路

基本DP题。我的代码是学DP之前写的,复杂度与DP都是O(N)。

代码

#include <stdio.h>int main(void)
{int n;long long a[1000000];int i;long long best, bestTmp;long long bestL, bestR, bestTmpL, bestTmpR;while (scanf("%d", &n) != EOF){if (n == 0)break;for (i=0; i<n; i++)scanf("%lld", &a[i]);best = a[0];bestL = bestR = 0;bestTmp = a[0];bestTmpL = bestTmpR = 0;for (i=1; i<n; i++){if (bestTmp < 0){bestTmp = a[i];bestTmpL = bestTmpR = i;}else{bestTmp += a[i];bestTmpR = i;}if (bestTmp > best){best = bestTmp;bestL = bestTmpL;bestR = bestTmpR;}}printf("%lld %lld %lld\n", best, bestL, bestR);}return 0;
}
/**************************************************************Problem: 1372User: liangrx06Language: CResult: AcceptedTime:470 msMemory:8652 kb
****************************************************************/

1373:整数中1出现的次数

http://ac.jobdu.com/problem.php?pid=1373

题意

输出a和b之间数字1出现的次数。

思路

分别求1-(a-1)和1-b之间1出现的次数,两者想减。

代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>int count(char *s, int a)
{int n = strlen(s);int i;int res = 0;int pow10i = 1;int si;for (i=0; i<n; i++){res += a/(pow10i*10)*pow10i;si = n-1-i;if (s[si] > '1')res += pow10i;if (s[si] == '1')res += a%pow10i + 1;//printf("i=%d, a=%d, pow10i=%d, res=%d\n", i, a, pow10i, res);pow10i *= 10;}return res;
}int main()
{int i;char sa[11], sb[11];int a, b;while(scanf("%s%s", sa, sb) != EOF){a = atoi(sa);b = atoi(sb);if (a > b){int tmp = a;a = b;b = tmp;char stmp[11];strcpy(stmp, sa);strcpy(sa, sb);strcpy(sb, stmp);}int counta = 0;int tmpa = a;for (i=0; i<strlen(sa); i++){if (tmpa%10 == 1)counta ++;tmpa /= 10;}int count0toa = count(sa, a);int count0tob = count(sb, b);printf("%d\n", count0tob - count0toa + counta);}return 0;
}
/**************************************************************Problem: 1373User: liangrx06Language: CResult: AcceptedTime:0 msMemory:912 kb
****************************************************************/

1374:所有员工年龄排序

http://ac.jobdu.com/problem.php?pid=1374

题意

公司内员工年龄排序。

思路

此题特点是age取值范围为(1<=age<=99),可用设置一数组统计每个age出现次数。算法复杂度O(N)。
快排估计会超时。

代码

#include <stdio.h>
#include <string.h>#define N 1000000int main()
{
    int i, j, n;
    int a[N];
    int count[100];
    while(scanf("%d", &n) != EOF)
    {
        memset(count, 0, sizeof(count));
        for (i=0; i<n; i++)
        {
            scanf("%d", &a[i]);
            count[a[i]] ++;
        }
        for (i=1; i<100; i++)
        {
            for (j=0; j<count[i]; j++)
                printf("%d ", i);
        }
        printf("\n");
    }
    return 0;
}
/**************************************************************
    Problem: 1374
    User: liangrx06
    Language: C
    Result: Accepted
    Time:790 ms
    Memory:4748 kb
****************************************************************/

1375:陈博的完美主义

http://ac.jobdu.com/problem.php?pid=1375

题意

对于一个整数序列d1, d2, d3 … dn,你是否能够算出至少改变其中的几个数,才能把他们变成从1到N的一个排列?

思路

统计1-N中数未出现得个数就是答案。

代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>#define N 100000
#define M 100int main()
{int i, n;int a[N], b[N+1];char s[M+1];while(scanf("%d", &n) != EOF){memset(b, 0, sizeof(b));for (i=0; i<n; i++){scanf("%s", s);if (strlen(s) > 9)a[i] = 0;elsea[i] = atoi(s);if (a[i] <= n && a[i] >= 1)b[a[i]]++;}int count = 0;for (i=1; i<=n; i++){if (b[i] > 0)count ++;}printf("%d\n", n-count);}return 0;
}
/**************************************************************Problem: 1375User: liangrx06Language: CResult: AcceptedTime:170 msMemory:1232 kb
****************************************************************/

这篇关于九度OJ 1371(排序) 1372(DP) 1373(统计) 1374(统计) 1375(统计)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/868688

相关文章

Pandas统计每行数据中的空值的方法示例

《Pandas统计每行数据中的空值的方法示例》处理缺失数据(NaN值)是一个非常常见的问题,本文主要介绍了Pandas统计每行数据中的空值的方法示例,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是空值?为什么要统计空值?准备工作创建示例数据统计每行空值数量进一步分析www.chinasem.cn处

Mysql如何将数据按照年月分组的统计

《Mysql如何将数据按照年月分组的统计》:本文主要介绍Mysql如何将数据按照年月分组的统计方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql将数据按照年月分组的统计要的效果方案总结Mysql将数据按照年月分组的统计要的效果方案① 使用 DA

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》:本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的

一文详解SQL Server如何跟踪自动统计信息更新

《一文详解SQLServer如何跟踪自动统计信息更新》SQLServer数据库中,我们都清楚统计信息对于优化器来说非常重要,所以本文就来和大家简单聊一聊SQLServer如何跟踪自动统计信息更新吧... SQL Server数据库中,我们都清楚统计信息对于优化器来说非常重要。一般情况下,我们会开启"自动更新

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法:数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高;分治法高效但实现复杂;位图法可读性差,但存储空间受限... 目录三种方法:方法概要数据库排序(http://www.chinasem.cn对数据库设备要求较高)分治法(常

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int

opencv实现像素统计的示例代码

《opencv实现像素统计的示例代码》本文介绍了OpenCV中统计图像像素信息的常用方法和函数,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 统计像素值的基本信息2. 统计像素值的直方图3. 统计像素值的总和4. 统计非零像素的数量