首页 > 试题广场 >

最优权重

[编程题]最优权重
  • 热度指数：109 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个未排序的整数数组, 需要给数组里每个元素一个整数权重值，权重值最小为1，相邻元素数字大的权重值也必须较大，那么整个数组的权重值总和最小为多少

输入描述:
未排序的整数数组


输出描述:
数组权重值最小总和
示例1

输入

2 1 2 2 3

输出

8

说明

为了满足要求，5个元素的权重值依次是2，1，2，1，2 这样最小总和就为8
算法知识视频讲解
添加回答
Foer头像 Foer
参考lc135题 分糖果
可在o(n)完成 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] n = sc.nextLine().split(" ");
        int len = n.length;
        int[] l_r = new int[len];
        int[] r_l = new int[len];
        Arrays.fill(l_r,1);
        Arrays.fill(r_l,1);
        for(int i = 1;i< len;i++){
            if(Integer.parseInt(n[i])>Integer.parseInt(n[i-1])){
                l_r[i] = l_r[i-1]+1;
            }
        }
        for(int i = len-2;i>=0;i--){
            if(Integer.parseInt(n[i])>Integer.parseInt(n[i+1])){
                r_l[i] = r_l[i+1]+1;
            }
        }
        int res = 0;
        for(int i = 0; i < len;i++){
            res+=Math.max(l_r[i],r_l[i]);
        }
        System.out.print(res);
    }
}


发表于 2021-05-12 14:33:20 回复(0)
牛客12312341头像 牛客12312341 
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+100;

int a[N];
int n;

#define pii pair<int,int>
int ans[N];
int main(){
    int x;
    while(cin>>x){
        a[++n]=x;
    }
    a[0]=a[n+1]=99999999;//为了方便操作把两边改成较为大的值
    priority_queue<pii> q;
    for(int i=1;i<=n;i++){
        q.push({-a[i],i});

//优先队列从小到大

    }
    
    while(!q.empty()){
        int i=q.top().second;q.pop();//获取最小的a[i]的下标
        if(a[i]>a[i+1]||a[i]>a[i-1]){
            if(a[i]>a[i+1]&&a[i]>a[i-1]) ans[i]=max(ans[i-1],ans[i+1])+1; //如果同时大于两边那么从数较大的更新
            else if(a[i]>a[i-1]) ans[i]=ans[i-1]+1;//如果旁边有数和a[i]相同则另一半更新就可以了
            else ans[i]=ans[i+1]+1;//同理
        }
        else ans[i]=1;//贪心直接最小
    }
    int res=0;
    for(int i=1;i<=n;i++) {
        res+=ans[i];//加起来
       // cout<<ans[i]<<" ";
    }
    cout<<res<<endl;
    return 0;
}

编辑于 2021-04-23 01:51:30 回复(0)
我才不是游客头像 我才不是游客
可以注意到每个数值的权值仅受其左右两侧的数值限制，而且很自然想到数组中最小的值权值一定是1。进一步想到，一个数字ai，如果它左右两侧数字都比它大，那么它的权值也可以设为1。
因此，将数组元素按值升序排序，并记录下标。枚举排序后的这些元素，更新这个元素和相邻元素的权值。 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct node
{
    int id,v;
    bool operator <(const node B)const
    {
        return v<B.v;
    }
} a[100005];
int n,b[100005],v[100005],ans;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    while(cin>>a[n+1].v) /**< a用来排序，b用来记录原始的数值 */
        a[n+1].id=n+1,n++,b[n]=a[n].v;
    sort(a+1,a+n+1);
    for(i=1; i<=n; i++)
    {
        int id=a[i].id;
        if(v[id]==0) /**< 如果id这个元素权值没给定过，那么它一定比它左右两端的小，可以置为1 */
            v[id]=1;
        if(id-1>0&&b[id]<b[id-1])/**< 检查下id这个元素能否更新其左右两侧的权值 */
            v[id-1]=max(v[id-1],v[id]+1);
        if(id+1<=n&&b[id]<b[id+1])
            v[id+1]=max(v[id+1],v[id]+1);
    }
    for(i=1; i<=n; i++)
        ans+=v[i];
    cout<<ans;
    return 0;
}


发表于 2021-04-17 11:38:49 回复(0)
提交观点

问题信息

iOS工程师 安卓工程师 哔哩哔哩 2021
上传者：小小
难度：
3条回答 1421浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号