首页 > 其他分享 >P4801题解

P4801题解

时间:2023-10-09 12:13:38浏览次数:43  
标签:饼干 int 题解 long t1 P4801 num ws

解题思路:

确实是一道很好的贪心,但由于加上了这个影响因素,使题目复杂度上升了不少。(考虑的东西多了嘛)

  1. 输个入。
  2. 对饼干温度无脑排序。
  3. 求最小值。
  4. 求最大值(用双指针做,后面会讲)。

解题过程:

先输入(这个步骤就不用我讲了

int a[1000005];
    long long n,ws;
    long long minn=0,num=ws;
    cin>>n>>ws;//输入饼干数和水温
    for(int i=1;i<=n;i++)
        cin>>a[i];

先排序!!

sort(a+1,a+n+1);

最容易的肯定就是最小值

!其实题意一定要读懂,我个提醒也是我自己看错的:

每当他吃一块饼干时,这块饼干的美味度为当前饼干与吃/喝的前一样食物(包括饼干和水)的温度的差的绝对值。


  • 那我们不妨分三种情况来考虑(ws 是水温):
  1. 当水温小于等于饼干中温度的最小值,此时喝好水后,从饼干中最小值一直按顺序(单调升序,前面排好序了)吃到最大值 (\(a_1,a_2\cdots a_n\)) 就是累计美味值最小的。
if(ws<=a[1]){
    minn=a[n]-ws;
}
  1. 水温大于等于饼干中温度的最大值时,喝好水后,按单调降序 (\(a_n,a_{n-1}\cdots a_1\)) 吃掉饼干可获得最小值。则有:
if(ws>=a[n]){
	minn=ws-a[1];
}
  1. 当 \(a_1\le ws\le a_n\) 时,直接 \(a_n-a_1\) 即可:
if(ws>=a[1]&&ws<=a[n]){
	minn=a[n]-a[1];
}

那么接下来是最大值:

前面也提到了要用双指针做,具体怎么实现呢?

先定义两个指针:

t1=1;t2=n;

因为排好序后,\(a_n-a_1\) 的跨度最大,然后 \(a_1-a_{n-1}\),再是 \(a_{n-1}-a_2\cdots\),以此类推,两个指针依次向中间靠拢,就可算出最大的美味值和了。

但是此时要考虑两点:

  1. 喝好水后应该先吃 \(a_n\) 还是 \(a_1\)。
  2. 在双指针的过程中,判断是喝了水后吃下一个饼干的美味值大还是直接吃美味值大。

所以我们要循环两次,分别为先吃 \(a_1\) 和先吃 \(a_n\),并在过程中判断上面所说的第2点。

则有

   long long num=ws;//存储上一个食物的温度
   long long ans2=0,ans=0;//分别分析取a[1]与a[n]为开头的情况(找最优解);
	ans+=abs(ws-a[t1]);
	num=a[t1];//从a[1]开始
	t1++;
	for(int i=2;i<=n;i++){
		if(i%2==0){
			ans+=max(abs(num-a[t2]),abs(ws-a[t2]));
			num=a[t2];
			t2--;
		}
		else{
			ans+=max(abs(num-a[t1]),abs(ws-a[t1]));
			num=a[t1];
			t1++;	
		}
	}
	t1=1;t2=n;//从a[n]开始
	ans2+=abs(ws-a[t2]);
	num=a[t2];
	t2--;
	for(int i=1;i<=n-1;i++){
		if(i%2==0){
			ans2+=max(abs(num-a[t2]),abs(ws-a[t2]));
			num=a[t2];
			t2--;
		}
		else{
			ans2+=max(abs(num-a[t1]),abs(ws-a[t1]));
			num=a[t1];
			t1++;
		}
	}
	ans=max(ans2,ans);//赋值最优解

到这里题就做完了,那——

AC 代码!

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
	long long n,ws;
	cin>>n>>ws;//输入饼干数和水温
	long long minn=0,num=ws;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);//排序!!!!
	long long cnt=1;
	long long t1=1,t2=n;
	if(ws<=a[1]){//判断最小值
    	minn=a[n]-ws;
	}
	else if(ws>=a[n]){
		minn=ws-a[1];
	}
	else{
		minn=a[n]-a[1];
	}
	long long ans2=0,ans=0;//判断最大值,分别分析取a[1]与a[n]为开头的情况(找最优解);
	ans+=abs(ws-a[t1]);
	num=a[t1];//存储上一个食物或水的温度
	t1++;
	for(int i=2;i<=n;i++){
		if(i%2==0){
			ans+=max(abs(num-a[t2]),abs(ws-a[t2]));
			num=a[t2];
			t2--;
		}
		else{
			ans+=max(abs(num-a[t1]),abs(ws-a[t1]));
			num=a[t1];
			t1++;	
		}
	}
	t1=1;t2=n;
	ans2+=abs(ws-a[t2]);
	num=a[t2];
	t2--;
	for(int i=1;i<=n-1;i++){
		if(i%2==0){
			ans2+=max(abs(num-a[t2]),abs(ws-a[t2]));
			num=a[t2];
			t2--;
		}
		else{
			ans2+=max(abs(num-a[t1]),abs(ws-a[t1]));
			num=a[t1];
			t1++;
		}
	}
	ans=max(ans2,ans);//取最优解
	cout<<minn<<" "<<ans;//华丽结束!
	return 0;
}

标签:饼干,int,题解,long,t1,P4801,num,ws
From: https://www.cnblogs.com/wyl123ly/p/p4801_solution.html

相关文章

  • Codeforces Round 902 (Div. 2) (CF1877) B、C、D 题解
    B题目大意你要传话给\(n\)个人,每传一下话需要花费\(p\),当一个人被传话后,他可以最多传给\(a_i\)个人,每次花费\(b_i\)。问把话传给\(n\)个人的最小花费。分析首先传给第一个人只少要\(p\)下来贪心,每次让花费最小、且能够传话的人去传话。考虑建一个堆,堆内的信息是......
  • 题解 尼克的任务
    有一种和题解区完全不同的做法。首先将所有任务按照时间从小到大排序,接着用\(f_i\)表示处理前\(i\)个任务所能得到的最大空闲时间。回顾一下需要满足的条件:再某个有任务的时刻,如果尼克是空闲的,就必须从中选择一个任务做。那么我们对于第\(i\)个任务,枚举上一个做的任务\(j......
  • P7710 [Ynoi2077] stdmxeypz 题解
    P7710[Ynoi2077]stdmxeypz题解我的第一道Ynoi题,体验感不高,调了大半天,最后发现有个地方\(B_1\)写成\(B_2\)了。分析树上问题,明显是要转到树下的,所以DFS序是一定要求的。有关树上距离,所以\(deep\)数组也是一定要求的。所以我们现在把问题转化成了:给你三个序列\(......
  • 「Round C10 B」间隔 题解
    简要题意本题有\(T\)组数据。给定一个由\(n\)个元素构成的正整数数列\(a_1,a_2,a_3...a_{n-1},a_n\)。问至少需要插入多少个整数才能使得\(a\)的各相邻元素之差相等(不能插入在头尾)。\(a\)数列保证是单调不减的。\(1\len\le10^6,0\lea_i\le10^6,1\leT\le1......
  • DBeaver [安装/问题解决]
     DBeaverMac版软件简介DBeaverMac版是一款专门为开发人员和数据库管理员设计的免费开源通用数据库工具。软件的易用性是它的宗旨,是经过精心设计和开发的数据库管理工具。免费、跨平台、基于开源框架和允许各种扩展写作(插件)。下载地址......
  • 【题解】CodeForces-1874/1875
    CodeForces-1875AJellyfishandUndertale一定是等待降到\(1\)或者能补满到\(a\)时才使用工具,依题意模拟即可。提交记录:Submission-CodeForcesCodeForces-1874AJellyfishandGame这种题目有点思路但是不是很会。赛时第一发写得根据奇偶性判断,\(k\)为偶数错了,然后感......
  • AtCoder Beginner Contest 323 (ABC 323) D、E、F 题解
    AtCoderBeginnerContest323(ABC323)D、E、F题解D题目大意给\(n\)种数\(s_i\),每一种数有\(c_i\)个,每次可以把两个相同的数合并为一个数,问最后会剩下多少数?分析对于每一个数\(s_i\),它最多被分解\(log_2c_i\)次,并且合并出来最大的数的大小小于\(s_i\timesc_i......
  • Hadoop问题解决(3)
    在启动hadoop过程中,出现如下错误:192.168.10.100:Invalidmaximumheapsize:-Xmx0m192.168.10.100:CouldnotcreatetheJavavirtualmachine.192.168.10.100:jobtracker已死,但pid文件仍存此时查看jobtracker的日志,1[root@ccloud100manager]#vim/var/log/hado......
  • hadoop问题解决(4)
    默认配置是将datanode,namenode,jobtracker,tasktracker,secondarynamenode的pid存放在/tmp目录下,随着linux的定期清理,这些pid就不见了,当然就无法停止了,怎么解决呢?在/tmp目录创建或者修改hadoop-hadoop用户名-datanode.pid 里面写入对应的pid, 可通过jps查看. namen......
  • 【UVA 12657】Boxes in a Line 题解(静态双向链表)
    您在编号为1的表格上有n个方框。n从左到右。您的任务是模拟4命令类型:•1XY:将框X向左移动到Y(如果X已经是Y的左侧,则忽略此项)•2XY:将框X向右移动到Y(如果X已经是Y的右侧,则忽略此项)•3XY:交换盒X和Y•4:反转整条线路。命令保证有效,即X不等于Y。例如,如果n=6,在执行114之后,该行......