D. Maxim and Array

原博客

http://codeforces.com/group/1EzrFFyOc0/contest/721/problem/D 题目

题意

给你n个数，你可以操作k次，每次使得一个数增加x或者减小x

你要使得最后所有数的乘积最小，问你最后这个序列长什么样子。

题解：

贪心，根据符号的不同，每次贪心的使得一个绝对值最小的数减去x或者加上x就好了

这个贪心比较显然。

假设当前乘积为ANS，那么你改变a[i]的大小的话，那么对答案的影响为ANS/A[i]/*X

然后找到影响最大的就好了。

 1 #include
 2 #include
 3 #include 
 4 #include
 5 #include
 6 #include
 7 #include<string>
 8 #include
 9 #include<set>
10 #include
11 #include
12 #include
13 #include
14 using namespace std;
15 #define ll long long
16 #define mem(a,x) memset(a,x,sizeof(a))
17 #define se second
18 #define fi first
19 const int INF= 0x3f3f3f3f;
20 const int N=2e5+5;
21 
22 ll n,k,x;
23 ll a[N];
24 
25 set< pair > s; //自动排序
26 
27 int main()
28 {
29     cin>>n>>k>>x;
30     bool flag=0; //负数的数目奇偶情况
31     for(ll i=1;i<=n;i++){
32         scanf("%lld",&a[i]);
33         if(a[i]<0)  flag^=1;//这技巧要记住
34         s.insert( make_pair (abs(a[i]),i) );//这技巧要记住
35     }
36     for(int i=1;i<=k;i++)
37     {
38         int j=s.begin()->second; //这技巧要记住
39         s.erase(s.begin());
40 
41         if(a[j]<0) flag^=1; //如果当前这个数是负数，负数数量减少1，讨论这个a[j]
42         if(!flag){ //除a[i]以外的 负数个数为偶数
43             a[j]-=x;
44         }
45         else{ //除a[i]以外的 负数个数为奇数
46             a[j]+=x;
47         }
48         if(a[j]<0) flag^=1; //再对改变后的a[j]讨论，如果是负的，负数数量+1；
49         s.insert( make_pair( abs(a[j]),j) );
50     }
51     for(int i=1;i<=n;i++)
52     {
53         cout<' ';
54     }
55 }

贪心思维

D. Maxim and Array

题意

题解：

相关

7个方法教你培养“成长型思维”

算法第四章《贪心策略》上机实践报告

【人工智能导论：模型与算法】第六章思维导图

洛谷 P2279 [HNOI2003]消防局的设立贪心

The 2021 CCPC Guilin Onsite【A,I,G(二分),D（思维+构造）,E（最短路】

codeforces和atcoder的思维题目

CF1479B Painting the Array（贪心+DP）

10张思维导图带你学习JavaScript

用象棋的思维趣说IT人的职业发展和钱途

cogs 1440. [NOIP2013]积木大赛贪心水题

天天快乐编程集训队2021暑假训练-0802-贪心题解

思维&榜样

标签