首页 > 代码库 > 【SPOJ-GSHOP】Rama and Friends【贪心】【细节】
【SPOJ-GSHOP】Rama and Friends【贪心】【细节】
题意:
给出n个非严格递增的整数(可能有负数),必须操作k次。每次能够把当中一个数变为它的相反数,使得终于的数列和最大。
输出这个最大和。
考验怎样出坑数据卡自己的程序...
#include <cstdio> const int maxn = 105; int n, k, num[maxn]; inline int iread() { int f = 1, x = 0; char ch = getchar(); for(; ch < '0' || ch > '9'; ch = getchar()) f = ch == '-' ? -1 : 1; for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; return f * x; } int main() { int T = iread(); while(T--) { n = iread(); k = iread(); int cnt = 0, sum = 0; for(int i = 1; i <= n; i++) { num[i] = iread(); cnt += (num[i] < 0); sum += num[i]; } if(k <= cnt) for(int i = 1; i <= k; i++) sum -= 2 * num[i]; else if(k > cnt) { for(int i = 1; i <= cnt; i++) sum -= 2 * num[i]; if(cnt == 0) sum -= ((k - cnt) & 1) * 2 * num[1]; else if(cnt < n) { if(-num[cnt] < num[cnt + 1]) sum += ((k - cnt) & 1) * 2 * num[cnt]; else sum -= ((k - cnt) & 1) * 2 * num[cnt + 1]; } else sum += ((k - cnt) & 1) * 2 * num[cnt]; } printf("%d\n", sum); } return 0; }
20 1 100 0 1 1 0 2 1 -9 -1 2 100 -9 -1 2 101 -9 -1 3 1 -3 -1 10 3 2 -3 -1 10 3 3 -3 -1 10 3 100 -3 -1 10 3 101 -3 -1 10 3 200 -3 -2 -1 5 200 -3 -2 -1 0 1 5 200 -3 -2 -1 4 5 5 7 0 1 2 3 4 6 4 -3 -2 -1 1 2 3 5 3 0 0 0 0 1 5 4 -2 -1 0 2 5 6 4 -30 -20 -10 100 100 200 6 4 -30 -20 -10 1 2 3 6 1 1 2 3 4 5 6
输出:
0 0 8 10 8 12 14 12 14 12 4 7 13 10 10 1 10 440 64 19
【SPOJ-GSHOP】Rama and Friends【贪心】【细节】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。