专栏首页刷题笔记1060 爱丁顿数 (25 分)

1060 爱丁顿数 (25 分)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/shiliang97/article/details/99892636

1060 爱丁顿数 (25 分)

英国天文学家爱丁顿很喜欢骑车。据说他为了炫耀自己的骑车功力,还定义了一个“爱丁顿数” E ,即满足有 E 天骑车超过 E 英里的最大整数 E。据说爱丁顿自己的 E等于87。

现给定某人 N 天的骑车距离,请你算出对应的爱丁顿数 E(≤N)。

输入格式:

输入第一行给出一个正整数 N (≤10​5​​),即连续骑车的天数;第二行给出 N 个非负整数,代表每天的骑车距离。

输出格式:

在一行中给出 N 天的爱丁顿数。

输入样例:

10
6 7 6 9 3 10 8 2 7 8

输出样例:

6

跟柳婼想的差不多,值得庆幸,但是具体实现想反了,有点坑踩到了。柳婼的法就没有坑...一会儿再说。选择大于努力

思路:

1.输入数据,直接排序从小大大(sort默认)

2.从最后一个开始判断如果第e个骑车公里数大于等于 n-e,那么有n-e个(就是第e个从小到大排,e后面的n-e个都比n-e大)(太乱了,还是柳神的好理解还短小)

3.并且 第e-1个比n-e小,说明满足了题目要求,输出n-e就行了

4.但是要考虑循环完无解,所以输出0 (测试点4)

5.边界值我考虑的比较乱 因为数组是从0 开始的 所以要加一减一啥的输出换算容易整蒙。所以最好申请多一个空间,数组直接从下标1开始就行了

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int n;
	cin>>n;
	vector<int>sum(n);
	for(int i=0;i<n;i++){
		cin>>sum[i];
	}sort(sum.begin(),sum.end());
	for(int i=n;i>=0;i--){
		if(sum[i]>n-i&&sum[i-1]<=n-i+1){
			cout<<n-i;
			return 0;
		}
	}
    cout<<0;
	
	return 0;
}

放柳神代码

虽然柳神代码和我一样长,但他的好理解。

1.从大到小排(和我反着的思路一样,不容易出错)

2.使用ans 和p两个变量进入while循环进行判断,跳出循环后直接输出

(避免了测试点4那个输出0的问题)

这个循环顺着走,条件就是题目给的也好理解

#include <iostream>
#include <algorithm>
using namespace std;
int a[1000000];
bool cmp1(int a, int b) {
    return a > b;
}
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a+1, a+n+1, cmp1);
    int ans = 0, p = 1;
    while(ans <= n && a[p] > p) {
        ans++;
        p++;
    }
    printf("%d", ans);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【map超时】【set超时】1-5 两个有序序列的中位数 (25 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • 【2019秋PAT乙级真题】7-4 天长地久 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • 【未完成】1068 万绿丛中一点红 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • 1060. 爱丁顿数(25)

    英国天文学家爱丁顿很喜欢骑车。据说他为了炫耀自己的骑车功力,还定义了一个“爱丁顿数”E,即满足有E天骑车超过E英里的最大整数E。据说爱丁顿自己的E等于87。

    AI那点小事
  • 【PAT乙级】爱丁顿数

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【BZOJ 1701】Cow School(斜率优化/动态凸包/分治优化)

    小牛参加了n个测试,第i个测试满分是??pi,它的得分是??ti。老师去掉??/??ti/pi最小的d个测试,将剩下的总得分/总满分作为小牛的得分。小牛想知道多...

    饶文津
  • 基数排序

    基数排序的排序原理不难理解,但是在算法设计上,个人感觉还是比那些常见的排序要难的,耐心慢慢一步步理解,还是比较容易看懂的,注意基数排序有两种,一种是高位优先,一...

    233333
  • Plus One

    问题:数组模拟整数加1 class Solution { public: vector<int> plusOne(vector<int> &digits...

    用户1624346
  • 1643 线段覆盖 3

    1643 线段覆盖 3 时间限制: 2 s 空间限制: 256000 KB 题目等级 : 黄金 Gold 题目描述 Description 在一个...

    attack
  • 洛谷P2831 愤怒的小鸟(状压dp)

    直接状压dp一下,\(f[sta]\)表示干掉\(sta\)这个集合里面的鸟的最小操作数

    attack

扫码关注云+社区

领取腾讯云代金券