头条前两题AC代码
#include<iostream>
#include<memory.h>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;
struct point{
int x;
int y;
bool operator< (const point &p){
if(p.x==x) return y<p.y;
else return x<p.x;
}
};
int main(){
int n;
cin>>n;
point a[500005];
for(int i=0;i<n;i++){
scanf("%d %d",&a[i].x,&a[i].y);
}
sort(a,a+n);
int maxy=a[n-1].y;
vector<int >v1;
vector<int >v2;
for(int i=n-1;i>=0;i--){
if(i==n-1) {
v1.push_back(a[i].x);
v2.push_back(a[i].y);
}
else if(a[i].y<maxy) continue;
else if(a[i].y>=maxy){
maxy=a[i].y;
v1.push_back(a[i].x);
v2.push_back(a[i].y);
}
}
for(int i=v1.size()-1;i>=0;i--){
//cout<<v1[i]<<" "<<v2[i]<<endl;
printf("%d %d\n",v1[i],v2[i]);
}
return 0;
}
注：cin输入会超时
#include<iostream>
//#include<vector>
#include<algorithm>
using namespace std;
long long int ans;
long long int a[500001];
//vector<long long int >v1;
void dfs(long long int start,long long int end){
if(start>end) return ;
if(start==end) {
long long int anss=a[start]*a[start];
if(anss>ans) ans=anss;
return ;
}
long long int sum=0;
long long int minn=1000000;
long long int flag=-1;
for(int i=start;i<=end;i++){
if(a[i]<minn) {
minn=a[i];
flag=i;
}
sum+=a[i];
}
long long int anss=sum*minn;
if(anss>ans) ans=anss;
dfs(start,flag-1);
dfs(flag+1,end);
return ;
}
int main(){
int n;
cin>>n;
long long int min=1000000;
long long int flag=0;
long long int sum=0;
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
sum+=a[i];
if(a[i]<min) {
min=a[i];
flag=i;
}
}
ans=sum*min;
dfs(0,flag-1);
dfs(flag+1,n-1);
cout<<ans;
}
联想公司福利 567人发布