seo排名优化培训网站,汽车网络营销推广方案,营销推广的平台,友情链接2598题目链接: https://nanti.jisuanke.com/t/36116 题目: 在蒜厂年会上有一个抽奖#xff0c;在一个环形的桌子上#xff0c;有 nn 个纸团#xff0c;每个纸团上写一个数字#xff0c;表示你可以获得多少蒜币。但是这个游戏比较坑#xff0c;里面竟然有负数#xff0c;表示你… 题目链接: https://nanti.jisuanke.com/t/36116 题目: 在蒜厂年会上有一个抽奖在一个环形的桌子上有 nn 个纸团每个纸团上写一个数字表示你可以获得多少蒜币。但是这个游戏比较坑里面竟然有负数表示你要支付多少蒜币。因为这些数字都是可见的所以大家都是不会出现的赔的情况。 游戏规则每人只能抓一次只能抓取一段连续的纸团所有纸团上的数字和就是你可以获得的蒜币。 蒜头君作为蒜厂的一员在想我怎么可以获得最多的蒜币呢最多能获取多少蒜币呢 因为年会是发奖那么一定有大于 00 的纸团。 输入格式 第一行输入一个整数 nn表示有 nn 个纸团。 第二行输入输入 nn 个整数 a_iai表示每个纸团上面写的数字这些纸团的输入顺序就是环形桌上纸团的摆放顺序。 输出格式 输出一个整数表示蒜头君最多能获取多少蒜币。 数据范围 对于 30\%30% 的数据1 \le n \le 10^2,-10^3 \le a_i \le 10^31≤n≤102,−103≤ai≤103。 对于 60\%60% 的数据1 \le n \le 5 \times 10^3,-10^6 \le a_i \le 10^61≤n≤5×103,−106≤ai≤106。 对于 100\%100% 的数据1 \le n \le 10^5,-10^9 \le a_i \le 10^91≤n≤105,−109≤ai≤109。 样例输入 3 1 -2 1 样例输出 2 题目来源 2019 蓝桥杯省赛 B 组模拟赛一 分析: 求循环的连续最大和. 循环好解决: 把数组首尾连成2n长的. 然后就是求长度不超过n的最大连续和. 一般求连续和 直接用前缀和,然后逐步做差即可. 但是这儿有个限制,要求长度不超过n. 所以我们可以用优先队列: 维护一个结构体 struct node { ll val; int index; }; 根据index判断一下长度是否超过n即可. #includebits/stdc.husing namespace std;typedef long long ll;const int maxn 1e550;ll arr[maxn * 2];struct node {ll val;int index;bool operator (const node a) const {if (val ! a.val) return val a.val;return index a.index;}node () {}node (ll vv, int ii) : val(vv), index(ii) {}
};int main() {ios::sync_with_stdio(false);int n;cin n;for (int i0; in; i)cin arr[i];for (int in; i2*n; i)arr[i] arr[i-n];for (int i1; i2*n; i)arr[i] arr[i] arr[i-1];ll res -8626213631111ll;ll tans;priority_queuenode pq;for (int i0; i2 * n; i) {if (pq.empty()) tans arr[i];if (tans res) res tans;while (!pq.empty()) {node tmp pq.top();if (i - tmp.index n) {pq.pop();continue;} else {tans arr[i] - tmp.val;break;}}if (tans res) res tans;pq.push({arr[i], i});}cout res endl;return 0;
} 转载于:https://www.cnblogs.com/cgjh/p/10343581.html
