首页 > 其他分享 >【寒假每日一题】AcWing 4818. 奶牛大学(补)

【寒假每日一题】AcWing 4818. 奶牛大学(补)

时间:2023-06-30 21:06:52浏览次数:50  
标签:入学 学费 4818 long 寒假 John Farmer 奶牛 AcWing


一、题目

1、原题链接

4818. 奶牛大学

2、题目描述

Farmer John 计划为奶牛们新开办一所大学! 有 N 头奶牛可能会入学。 每头奶牛最多愿意支付 ci 的学费。 Farmer John 可以设定所有奶牛入学需要支付的学费。 如果这笔学费大于一头奶牛愿意支付的最高金额,那么这头奶牛就不会入学。 Farmer John 想赚尽可能多的钱,从而可以给他的讲师提供一笔可观的工资。 请求出 他能赚到的钱的数量,以及此时 应当收取多少学费输入格式 输入的第一行包含 N。 第二行包含 N 个整数 c1,c2,…,cN,其中 ci是奶牛 i 愿意支付的最高学费金额。 输出格式 输出 Farmer John 可以赚到的最大金额以及最优情况下他应该收取的学费。如果有多个解,输出收取学费最小的解。 注意这个问题涉及到的整数可能需要使用 64 位整数型(例如,Java 中的 “long”,C/C++ 中的 “long long”)。 数据范围1≤N≤105,1≤ci≤106输入样例

4 1 6 4 6

输出样例

12 4

样例解释 如果 Farmer John 收费 4,那么 3 头奶牛将会入学,从而使他赚取 3×4=12的金额。

二、解题报告

思路来源: AcWing 4818. 奶牛大学(寒假每日一题2023) y总yyds

1、思路分析

(1)我们可以先将每头奶牛愿意支付的费用进行排序。 (2)如果收取的学费没有超过奶牛愿意支付的费用,则奶牛可以入学。求取入学奶牛数量就转化为了要求取奶牛愿意支付的费用序列中大于等于学费的个数,而学费可以不是整数。在奶牛入学数量一定时,我们希望学费在能满足这个入学数量的情况下,越大越好,也就是让学费恰好和当前入学数量中愿意支付钱数最少的那个奶牛所愿支付的钱数相等。而如果不是这样的话,我们的学费一定不是在满足这样入学数量时最大的。 (3)问题就转换成了:我们枚举(1)中序列的各个费用分别作为学费,来求此时的收益,其中收益最大即为所求,而学费就是求得此收益的学费。

2、时间复杂度

时间复杂度为O(n)

3、代码详解

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=100010;
LL c[N],n;
int main()
{   cin>>n;
    for(int i=0;i<n;i++){
    	cin>>c[i];
	}
	sort(c,c+n);
	LL ans=0,sum=0,p;
	for(int i=0;i<n;i++){
	   sum=(n-i)*c[i];
	   if(sum>ans){
	     ans=sum;	 
	   	 p=c[i];
	   }
	}
	cout<<ans<<" "<<p;
    return 0;
}

标签:入学,学费,4818,long,寒假,John,Farmer,奶牛,AcWing
From: https://blog.51cto.com/u_15720469/6593531

相关文章

  • 【寒假每日一题】AcWing 4728. 乘方
    目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解 一、题目1、原题链接4728.乘方-AcWing题库2、题目描述小文同学刚刚接触了信息学竞赛,有一天她遇到了这样一个题:给定正整数 a 和 b,求 a^b 的值是多少。a^b 即 b 个 a 相乘的值,例如......
  • AcWing 3662. 最大上升子序列和
    \(AcWing\)\(3662\).最大上升子序列和一、题目描述给定一个长度为\(n\)的整数序列\(a_1,a_2,…,a_n\)。请你选出一个该序列的严格上升子序列,要求所选子序列的各元素之和尽可能大。请问这个最大值是多少?输入格式第一行包含整数\(n\)。第二行包含\(n\)个整数\(a_......
  • 【寒假每日一题】AcWing 4644. 求和(补)
    目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解 一、题目1、原题链接4644.求和-AcWing题库2、题目描述给定 n个整数 a1,a2,⋅⋅⋅,an,求它们两两相乘再相加的和,即S=a1⋅a2+a1⋅a3+⋅⋅⋅+a1⋅an+a2⋅a3+⋅⋅⋅+an−2⋅an−1+an−2⋅an+a......
  • 算法刷题记录:AcWing 4908. 饥饿的牛
    目录题目链接:题目分析:时间复杂度SF代码AC代码:题目链接:https://www.acwing.com/problem/content/description/4911/题目分析:数据范围最大\(10^{14}\),所以如果采用枚举一定会TLE,因为只有\(10^5\)天会运来新的草,所以我们可以只考虑运草的天。假设当前到\(d_2\)天之前剩余干......
  • 【寒假每日一题】AcWing 3443. 学分绩点(补)
    目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解 一、题目1、原题链接3443.学分绩点-AcWing题库2、题目描述北京大学对本科生的成绩施行平均学分绩点制(GPA)。既将学生的实际考分根据不同的学科的不同学分按一定的公式进行计算。公式如下:实......
  • 【寒假每日一题】AcWing 3400. 统计次数(补)
     目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解 一、题目1、原题链接3400.统计次数-AcWing题库2、题目描述给定两个正整数 n 和 k,求从 1 到 n 这 n 个正整数的十进制表示中 k 出现的次数。输入格式共一行,包含两个整数 n ......
  • Acwing 4440 照相
    Acwing4440照相原题指路因为序列长为偶数,考虑将牛进行两两分组为什么要将其进行两两分组:因为题目按偶数前缀进行反转,每一组中的牛总是相邻的,不会被拆散。两两分组后会有四种情况:GGHHGHHG我们再观察可得:每次反转,就是将每组内的两头牛进行互换如:而GGHH反转并......
  • AcWing——凑数(二进制中1的个数)
    1、题目初始时,n=0。每一轮操作都要依次完成两个步骤:第一步,任选一个非负整数a,将n增加a,这一步所需付出的代价为a。第二步,将n乘以2,这一步无需付出任何代价。你可以不断重复上述操作。给定一个整数x,你的任务是使n在某一步操作后(不一定是某一轮结束后)恰好等于x且付出的总代......
  • 【蓝桥杯集训·周赛】AcWing 第96场周赛
    第一题AcWing4876.完美数一、题目1、原题链接4876.完美数2、题目描述如果一个正整数能够被2520整除,则称该数为完美数。给定一个正整数n,请你计算[1,n]范围内有多少个完美数。输入格式一个整数n。输出格式一个整数,表示[1,n]范围内完美数的个数。数据范围前3个测试点满......
  • 【蓝桥杯集训·周赛】AcWing 第 95 场周赛
    第一题AcWing4873.简单计算一、题目1、原题链接4873.简单计算2、题目描述给定四个整数x1,y1,x2,y2,请你计算max(|x1−x2|,|y1−y2|)。输入格式第一行包含两个整数x1,y1。第二行包含两个整数x2,y2。输出格式一个整数,表示max(|x1−x2|,|y1−y2|)的值。数据范围前4个测试点......