526互联

维护除了自己外的最大值

发布时间 2023-08-11 02:06:13作者: potential-star

AcWing 5132. 奶牛照相

对于求除了当前点外其他点的最大值，

  • 1.笨拙的方法是维护最大值和次大值以及他们所对应的坐标，用pair可以实现。
  • 2.巧妙的办法是用前缀数组和后缀数组预处理

1的实现

#include <bits/stdc++.h>
using namespace std;
# define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
const int N = 2e5 + 10;
const int M = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;

int n, m;
int ans[N];
int h[N],w[N];

vector<pii>v;
bool cmp(pii d,pii e){
    return d.first>e.first;
}
signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t;
   t=1;
    while (t--) {
cin>>n;
int s=0;
for(int i=1;i<=n;i++){cin>>w[i]>>h[i];
    s+=w[i];
    v.push_back({h[i],i});
}
sort(v.begin(),v.end(),cmp);
for(int i=1;i<=n;i++){
    if(h[i]==v[0].first&&i==v[0].second){
        ans[i]=v[1].first;
    }
    else ans[i]=v[0].first;
}

for(int i=1;i<=n;i++){
    cout<<(ll)ans[i]*(s-w[i])<<" ";
}
    }
    return 0;
}
  • 方法2
#include <bits/stdc++.h>
using namespace std;
# define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
const int N = 2e5 + 10;
const int M = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;

int n, m;
int ans[N];
int h[N],w[N];
int l[N],r[N];

bool cmp(pii d,pii e){
    return d.first>e.first;
}
signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t;
   t=1;
    while (t--) {
cin>>n;
int s=0;
for(int i=1;i<=n;i++){cin>>w[i]>>h[i];
    s+=w[i];
    l[i]=max(h[i],l[i-1]);
}
for(int i=n;i>=1;i--)r[i]=max(h[i],r[i+1]);


for(int i=1;i<=n;i++){
    int ans=max(l[i-1],r[i+1]);
    cout<<(ll)ans*(s-w[i])<<" ";
}
    }
    return 0;
}