瑞安网站建设,wordpress整合discu,网站建好了怎么做淘宝客,技术支持 滕州网站建设#x1f680;前言 #x1f680; 大家好啊#xff0c;这里是幸麟 #x1f9e9; 一名普通的大学牲#xff0c;最近在学习算法 #x1f9e9;每日一题的话难度的话是根据博主水平来找的 #x1f9e9;所以可能难度比较低#xff0c;以后会慢慢提高难度的 #x1f9e9;此题标… 前言 大家好啊这里是幸麟 一名普通的大学牲最近在学习算法 每日一题的话难度的话是根据博主水平来找的 所以可能难度比较低以后会慢慢提高难度的 此题标签*1500 数据结构 贪心 本文栏目一起来打cf吧 期待各位的点赞收藏关注订阅专栏每天一起写一道cf吧 一起学习算法吧 往期链接 B. Coloring—codeforces每日一题http://t.csdn.cn/eEkkb N. Number Reduction—codeforces每日一题 http://t.csdn.cn/jCLEg E. Easy Assembly—codeforces每日一道思维题2 http://t.csdn.cn/pNrCd codeforces每日一题1-Absolute Sorting http://t.csdn.cn/mCL6Y 题目
题目链接Problem - C - Codeforces
题目 题目大意
Baltic有一个数组a里面的元素个数是n因为他喜欢数字m(1mn2e510)所以他希望a1a2a3.....ama1a2....ak1kn)
为实现他的希望他可以进行以下的操作也可以不进行
选中数组其中一个元素的下标i令a[i]-a[i];
请问他至少进行多少次操作才能实现a1a2a3.....ama1a2....ak1kn) 输入每个测试用例的第一行包含两个整数 n和m1≤m≤n≤2⋅105 — Baltic数组a的大小和他最喜欢的数字。 第二行包含 n个整数 保证 n 的和 在所有测试用例中不超过 2⋅105 输出每一个用例最小的操作数 往下面翻就是答案了想继续思考的话还是不要往下面翻了 思路答案
既然想要实现a1a2a3.....ama1a2....ak1kn)
我们令sum[i]为a1a2a3.....ai
假设im 此时我们令a[i1]a[i2]...a[m]为subsum你可以理解为sum[m]-sum[i])
如果有subsum0,那么sum[m]sum[i]
如果对于任何一个im有subsum0,那么就有sum[m]sum[i](1im)
那么要实现这一部分我们就要维护这个subsum使其永远0即可
那么只要每次出现subsum0的情况我们需要减去我们之前遍历过的最大的正数因为操作数要最小所以我们尽量减去最大的正数这里我使用了优先队列
那么经过如上操作我们就使用了最少的操作数完成了前半部分a1a2a3.....ama1a2....ak1km)
那么后半部分我们也同理详情可以看一下代码上面讲的可能有点抽象了
#include iostream
#include queue
#include map
#include unordered_map
#include vector
#include algorithm
#include cmath
#include string
#include cstring
#include set
using namespace std;
typedef long long ll;
const int N2e510;ll a[N];
int main()
{int t;cint;while(t--){priority_queuell q1;priority_queuell q2;int n,m;int ans0;scanf(%d %d,n,m);for(int i1;in;i){scanf(%lld,ai);}if(n1){cout0\n;continue;}ll subsum0;for(int im;i1;i--){subsumsubsuma[i];if(a[i]0){q1.push(a[i]);}if(subsum0){ans;subsumsubsum-2*q1.top();q1.pop();}}ll addsum0;for(int im1;in;i){addsuma[i];if(a[i]0){q2.push(-a[i]);}if(addsum0){ans;ll numq2.top();addsum2*num;q2.pop();}}coutans\n;}return 0;
}好了今天的每日一题到此结束了有些地方说的可能不太清楚如果有疑惑欢迎在评论区留言
一起讨论一下最近会继续写题目但是不会更新这个系列了等期末考结束再来吧
