给定一个未排序的整数数组, 需要给数组里每个元素一个整数权重值,权重值最小为1,相邻元素数字大的权重值也必须较大,那么整个数组的权重值总和最小为多少
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); } }
#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; }
#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; }