深圳龙岗区地图,重庆优化网站,做公司,做网站无赖客户退款最大数组和 算法思路#xff1a;利用前缀和化简 for 循环将 n^2 简化成 nn#xff0c;以空间换时间。枚举每个 m#xff0c;m是删除最小两个数#xff0c;那k-m就是删除最大数#xff0c;mk#xff0c;求和最大的值。暴力就是枚举 m-O(n)#xff0c;计算前 n-(k-m)的…最大数组和 算法思路利用前缀和化简 for 循环将 n^2 简化成 nn以空间换时间。枚举每个 mm是删除最小两个数那k-m就是删除最大数mk求和最大的值。暴力就是枚举 m-O(n)计算前 n-(k-m)的和减去前 2*m 的和O(nn)。前缀和能化简求前 n 个和的过程变成 O(1)的复杂度因为前缀和能够直接进行直接查询。 #includebits/stdc.h
using namespace std;
typedef long long LL;
const int N 2e510;LL a[N];
int t,n,k;
LL sum[N];int main( ){cint;while(t--){memset(a, 0, sizeof(a));memset(sum, 0, sizeof(sum));cinnk;for(int i1;in;i)cina[i];sort(a1,a1n);for(int i1;in;i)sum[i]a[i]sum[i-1];LL ans 0;for(int m0;mk;m){ans max(ans,sum[n-(k-m)]-sum[2*m]);}coutansendl;}return 0;
}可以利用 vector 化简代码不过数组下标要从 0开始。 视野总和
描叙有n个人站队所有的人全部向右看个子高的可以看到个子低的发型给出每个人的身高问所有人能看到其他人发现总和是多少。 输入4 3 7 1 输出2
思路设置单调递减栈复杂度 On如果暴力复杂度 On^2
#includebits/stdc.h
using namespace std;
stackint st;
const int N 1e5 10;
int n;
int a[N];
int main( ){cinn;for(int i1;in;i)cina[i];int ans 0;for(int i1;in;i){if(st.empty()||st.top()a[i])st.push(a[i]);else{while(!st.empty()st.top()a[i]){st.pop();ans;}st.push(a[i]);if(st.empty())ans--;}}coutansendl;return 0;
}柱状图中的最大矩形
柱状图中的最大矩形
#includebits/stdc.h
using namespace std;
const int N 1e5 10;
int n;
int a[N];
vectorint heights;
int main( ){cinn;for(int i1;in;i)cina[i];int ans 0;for(int i1;in;i){int wide1;for(int ji-1;j1;j--){if(a[j]a[i])wide;}for(int ji1;jn;j){if(a[j]a[i])wide;}ans max(ans,wide*a[i]);}coutans\n;return 0;
}四元组问题 青茶绿梅*2博主讲的很好 暴力做法 n^4 能过 50%所以需要进行优化这题需要 n 或 nlogn 的时间复杂度。 算法思路将四元组问题转化成三元组单调递减栈前缀和问题。假设前三个元素已经知道那只需要找到小于 c 的 d 则四元组存在利用后缀和来得到c后面的最小值作为 d。然后找前三元组前三元组的 abc 的曲线画出来有利于理解。算法思路将一个元素入栈然后从左到右依次与栈顶判断如果小于栈顶入栈如果大于栈顶则出栈直到小于栈顶或栈元素为空这时最后一个出栈的为 a入栈元素为 b如果接下来继续操作找到比栈顶元素大则继续刚才过程同时更细 a 与 b如果找到比栈顶元素小则为 c 可以查询后缀和判断是否有 d 的存在。栈顶元素是目前最大的 b。 模拟一下1000 333 222 888 999 100 50 #includebits/stdc.h
using namespace std;
const int N 5e5 10;
int n;
int nums[N];
stackint st;
int main( ){cinn;for(int i1;in;i)cinnums[i];int kINT_MIN;vectorintmin_r(n,INT_MAX);for (int in-1; i1; i--) {min_r[i] min(min_r[i1],nums[i]);}for(int i1;in;i){if(knums[i]nums[i]min_r[i]){coutYES;return 0;}while(!st.empty()st.top()nums[i]){k max(k,nums[i]);st.pop();}st.push(nums[i]);}coutNO;return 0;
}
