第二届跨界杯预赛 B 题贪心算法橙色问题
最编程
2024-05-01 20:11:47
...
这道题的题解一定要最早写,因为真的坑死我了这题
其实B题是最早切的,我记得那天比赛上来先看的A题,一看这么长我的天哪,再一看B题,又短又漂亮,赶紧先做B题,但是上来遇到了一点语言的问题,说起来还是STL不太熟悉,然后疯狂查书,浪费了很多时间,后来又半途而废先切了C
B题已经被收进洛谷的题库了,P6364
B题链接
我开始的想法是把同学的成绩放到一个数组中,然后再单开一个辅助数组存放同学们的橙子数,不断从第一个数组中找最小值下标,然后根据这个最小下标的左右同学的成绩来判断他的橙子数,如果比左右的同学大,那就在左右同学的基础上取大的那个++;
之后再把这个数从数组中忽略,重复上述工作
然而我忽略了一个非常重要的事情QAQ,那就是找最小下标的时候,可能要用一个ON的时间复杂度,然后贪心需要ON的时间复杂度,导致直接复杂度爆炸,然而我当时坚信一定要找最小下标,QAQ。
附上第一次的渣渣代码(错误示范)
#include<bits/stdc++.h>
using namespace std;
#define ios std::ios::sync_with_stdio(false)
int B[1000505];
int A[1000505];
long long n;
long long temp=0;
int sum=0;
int find_min(int m,int n,int * A)
{
int i;
int cnt;
int zuixiao=*max_element(A,A+n+1);
// for(int i=0;i<9;i++)
// {
// cout<<A[i]<<' ';
// }
for( i=m;i<=n;i++)
{
if(A[i]!=-1)
{
if(A[i]<=zuixiao)
{
zuixiao=A[i];
cnt=i;
}
}
}
temp=cnt;
return cnt;
}
signed main(int argc, const char * argv[])
{
ios;
int index;
cin>>n;
for(int i=1;i<n+1;i++)
{
cin>>A[i];
}
for(int i=0;i<n;i++)
{
index=find_min(1,n,A);
if(B[index-1]==0&&B[index+1]==0)
{
B[index]=1;//如果左右都没有直接写1
}
if(B[index-1]!=0&&B[index+1]==0)
{
if(A[index]>A[index-1])
{
B[index]=B[index-1]+1;//如果有一边的话就分三种情况
}
if(A[index]<A[index-1])
{
B[index]=1;
}
if(A[index]==A[index-1])
{
B[index]=B[index-1];
}
}
if(B[index+1]!=0&&B[index-1]==0)
{
if(A[index]>A[index+1])
{
B[index]=B[index+1]+1;
}
if(A[index]<A[index+1])
{
B[index]=1;
}
if(A[index]==A[index+1])
{
B[index]=B[index+1];
}
}
if(B[index-1]!=0&&B[index+1]!=0)
{
if(A[index]==A[index-1])
{
B[index]==B[index-1];
}
if(A[index]==A[index+1])
{
B[index]==B[index+1];
}
if(A[index]<A[index-1]&&A[index]<A[index+1])
{
B[index]=1;
}
if(A[index]>A[index-1]&&A[index]>A[index+1])
{
if(A[index-1]>=A[index+1])
{
B[index]=B[index-1]+1;
}
else
{
B[index]=B[index+1]+1;
}
}
if(A[index]>A[index-1])
{
B[index]=B[index-1]+1;
}
}
// for(int i=0;i<9;i++)
// {
// cout<<A[i]<<' '<<endl;
// }
// for(int i=1;i<n+1;i++)
// {
// cout<<B[i]<<' ';
// }
// cout<<endl;
A[temp]=-1;
// for(int i=1;i<n+1;i++)
// {
// cout<<A[i]<<' ';
// }
// cout<<endl;
}
for(int i=1;i<n+1;i++)
{
sum=sum+B[i];
}
cout<<sum;
return 0;
}
借用@RXZ的话来说就是 又臭又长,一定不是好代码
于是这道题就遗恨未解出
其实这道题没有那么复杂,直接贪心就好了,但是因为左右两端都会影响,所以要从左到右一次,从右到左一次,贪心两次,然后取相对大的那个值。
注意数组可以开int ,但是橙子数很可能会超过,所以要用LL;
学到了一个新的函数 MAX(A,B),用来比较大小很爽
附上修改后AC代码
#include<bits/stdc++.h>
using namespace std;
#define ios std::ios::sync_with_stdio(false);
#define ll long long
#define loop(i,a,n) for(int i=a;i<n;i++)
const int N=1e6+10;
int data[N];
int a[N];//从左到右贪心的数组
int b[N];//从右到左贪心的数组
int n;
ll sum;
signed main()
{
ios;
cin>>n;
loop(i,0,n)
{
cin>>data[i];
}
// loop(i,0,n)
// cout<<data[i]<<' ';
// cout<<endl;
loop(i,0,n)
{
a[i]=1;
b[i]=1;//开始的时候初值都是1
}
loop(i,1,n)
{//从左到右贪心
if(data[i-1]<data[i])
a[i]=a[i-1]+1;//如果更大就在左边的基础上加一
if(data[i-1]==data[i])
a[i]=a[i-1];//
}
for(int i=n-1;i>=0;i--)
{
//从右往左贪心
if(data[i]>data[i+1])
b[i]=b[i+1]+1;//如果更大就在右边的基础上加一
if(data[i]==data[i+1])
b[i]=b[i+1] ;
}
loop(i,0,n)
{
sum=sum+max(a[i],b[i]);
}
// loop(i,0,n)
// {
// cout<<a[i]<<' ';
// }
// cout<<endl;
// loop(i,0,n)
// {
// cout<<b[i]<<' ';
// }
// cout<<endl;
cout<<sum;
return 0;
}
用了一些宏定义让代码更加漂亮,请各位观众自行判断
我是冷萃泡泡茶,一个蒟蒻
推荐阅读