解题思路:
确实是一道很好的贪心,但由于加上了水这个影响因素,使题目复杂度上升了不少。(考虑的东西多了嘛)
- 输个入。
- 对饼干温度
无脑排序。 - 求最小值。
- 求最大值(用双指针做,后面会讲)。
解题过程:
先输入(这个步骤就不用我讲了)
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 是水温):
- 当水温小于等于饼干中温度的最小值,此时喝好水后,从饼干中最小值一直按顺序(单调升序,前面排好序了)吃到最大值 (\(a_1,a_2\cdots a_n\)) 就是累计美味值最小的。
if(ws<=a[1]){
minn=a[n]-ws;
}
- 水温大于等于饼干中温度的最大值时,喝好水后,按单调降序 (\(a_n,a_{n-1}\cdots a_1\)) 吃掉饼干可获得最小值。则有:
if(ws>=a[n]){
minn=ws-a[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\),以此类推,两个指针依次向中间靠拢,就可算出最大的美味值和了。
但是此时要考虑两点:
- 喝好水后应该先吃 \(a_n\) 还是 \(a_1\)。
- 在双指针的过程中,判断是喝了水后吃下一个饼干的美味值大还是直接吃美味值大。
所以我们要循环两次,分别为先吃 \(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