Codeforces #374 721D. Maxim and Array

正文索引 [隐藏]

题目翻译
题解
代码

传送门：http://codeforces.com/problemset/problem/721/D

题目翻译

有一个长度为N的序列，每个操作可以给任意一个数+x/-x，至多进行k次操作，使序列乘积最小，输出方案。

题解

一个大讨论 + 线段树

如果序列里0的数量比操作数多，那么序列的乘积一定为0.直接输出，结束
如果序列里存在0，那么我们可以用其中的一个0把序列里的负数个数调成奇数个，其他0全部变成整数。转到4 。
我们找序列里正数最小/负数最大的那个数，然后看看能不能通过操作把他的符号倒置，如果不行，那么就用全部操作使这个数的绝对值最小即可，输出，结束。如果可以，那么把这个数的符号倒置，转到4。
因为存在奇数个负数，所以我们要使每个数绝对值乘积最大，秉承和一定积最大的原则，我们用每个数的绝对值建一颗线段树，然后每次给绝对值最小的数 + X ，暴力执行完剩余的操作次数。然后按照正负输出即可。

代码

//while(true) RP++;
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int Maxn = 200000;
int n;
LL k,T;
LL num[Maxn + 5];
LL ff[Maxn + 5];
struct Btree
{
    int left,right;
    LL min;
    int pos;
};
Btree tree[Maxn * 4 + 5];
inline void update(int x)
{
    if (tree[x].left == tree[x].right) return ;
    if (tree[x * 2].min < tree[x * 2 + 1].min)
    {
        tree[x].min = tree[x * 2].min;
        tree[x].pos = tree[x * 2].pos;
    }
    else
    {
        tree[x].min = tree[x * 2 + 1].min;
        tree[x].pos = tree[x * 2 + 1].pos;
    }
}
inline void build(int x, int left, int right)
{
    tree[x].left = left;
    tree[x].right = right;
    if (left == right)
    {
        tree[x].min = num[left];
        tree[x].pos = left;
    }
    else
    {
        int mid=(left + right) / 2;
        build(x * 2, left, mid);
        build(x * 2 + 1, mid + 1, right);
        update(x);
    }
}
void addTree(int x,int pos,int val)
{
    if (tree[x].left == tree[x].right)
    {
        tree[x].min += val;
    }
    else
    {
        int mid = (tree[x].left + tree[x].right) / 2;
        if (pos <= mid) addTree(x * 2, pos, val);
        if (mid + 1 <= pos) addTree(x * 2 + 1, pos, val);
        update(x);
    }
}
inline LL judge(LL mid)
{
    LL ret = 0;
    for (int i = 1; i <= n; i++)
    {
        if (num[i] < mid)
            ret = ret + (num[i] - mid) / k + ((num[i] - mid) % k == 0 ? 0 : 1);
    }
    return ret;
}
inline void maxPossible()
{
    if (T == 0) return ;
    for (int i = 1; i <= n; i++)
    {
        if (num[i] < 0)
        {
            ff[i] = -1;
            num[i] = -num[i];
        }
        else
        {
            ff[i] = 1;
        }
    }
    build(1,1,n);
    for (int rt = 1; rt <= T; rt++)
    {
        int minPos = tree[1].pos;
        num[minPos] += k;
        addTree(1,minPos,k);
    }
    for (int i = 1; i <= n; i++)
        num[i] = num[i] * ff[i];
}
int main()
{
    scanf("%d%I64d%I64d", &n, &T, &k);
    for (int i = 1; i <= n; i++)
        scanf("%I64d", &num[i]);
    int flagF = 0, flagZ = 0;
    for (int i = 1; i <= n; i++)
    {
        if (num[i] == 0) flagZ++;
        if (num[i] < 0) flagF++;
    }
    //积只能为0
    if (flagZ > T)
    {
        for (int i = 1; i <= n; i++)
        {
            if (num[i] == 0 && T > 0)
            {
                num[i] -= k;
                T--;
            }
            if (i == n) printf("%I64d\n",num[i]); else printf("%I64d ",num[i]);
        }
        return 0;
    }
    if (flagZ > 0)
    {
        if (flagF & 1)
        {
            //0 -> 正数
            for (int i = 1; i <= n; i++)
                if (num[i] == 0)
                {
                    num[i] += k;
                    T--;
                }
        }
        else
        {
            //一个0 -> 正数
            bool flag = true;
            for (int i = 1;i <= n; i++)
                if (num[i] == 0)
                {
                    if (flag)
                    {
                        num[i] -= k;
                        flag = false;
                    }
                    else
                    {
                        num[i] += k;
                    }
                    T--;
                }
        }
        maxPossible();
        for (int i = 1; i <= n; i++)
            if (i == n) printf("%I64d\n",num[i]); else printf("%I64d ",num[i]);
        return 0;
    }
    if (flagF&1)
    {
        //负数乘积尽量大
        maxPossible();
        for (int i = 1; i <= n; i++)
            if (i == n) printf("%I64d\n",num[i]); else printf("%I64d ",num[i]);
        return 0;
    }
    //正数乘积尽量小
    int maxFPos = -1,minZPos = -1;
    for (int i = 1; i <= n; i++)
    {
        if (num[i] > 0)
        {
            if (minZPos == -1 || num[minZPos] > num[i]) minZPos = i;
        }
        else
        {
            if (maxFPos == -1 || num[maxFPos] < num[i] ) maxFPos = i;
        }
    }
    if (maxFPos == -1) num[maxFPos=200001]=-1e9-1;
    if (minZPos == -1) num[minZPos=200001]=1e9+1;
    LL delta = min(-num[maxFPos], num[minZPos]);
    if (delta / k + 1 <= T)
    {
        if (-num[maxFPos] > num[minZPos])
        {
            num[minZPos] -= (delta / k + 1) * k;
            T -= delta / k + 1;
        }
        else
        {
            num[maxFPos] += (delta / k + 1) * k;
            T -= delta / k + 1;
        }
        //负数乘积尽量大
        maxPossible();
        for (int i = 1; i <= n; i++)
            if (i == n) printf("%I64d\n",num[i]); else printf("%I64d ",num[i]);
        return 0;
    }
    else
    {
        if (-num[maxFPos] > num[minZPos])
        {
            num[minZPos] -= T * k;
        }
        else
        {
            num[maxFPos] += T * k;
        }
        for (int i = 1; i <= n; i++)
            if (i == n) printf("%I64d\n",num[i]); else printf("%I64d ",num[i]);
        return 0;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

//while(true) RP++;

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define LL long long

using namespace std;

const int Maxn = 200000;

int n;

LL k,T;

LL num[Maxn + 5];

LL ff[Maxn + 5];

struct Btree

{

int left,right;

LL min;

int pos;

};

Btree tree[Maxn * 4 + 5];

inline void update(int x)

{

if (tree[x].left == tree[x].right) return ;

if (tree[x * 2].min < tree[x * 2 + 1].min)

{

tree[x].min = tree[x * 2].min;

tree[x].pos = tree[x * 2].pos;

}

else

{

tree[x].min = tree[x * 2 + 1].min;

tree[x].pos = tree[x * 2 + 1].pos;

}

inline void build(int x, int left, int right)

{

tree[x].left = left;

tree[x].right = right;

if (left == right)

{

tree[x].min = num[left];

tree[x].pos = left;

}

else

{

int mid=(left + right) / 2;

build(x * 2, left, mid);

build(x * 2 + 1, mid + 1, right);

update(x);

}

void addTree(int x,int pos,int val)

{

if (tree[x].left == tree[x].right)

{

tree[x].min += val;

}

else

{

int mid = (tree[x].left + tree[x].right) / 2;

if (pos <= mid) addTree(x * 2, pos, val);

if (mid + 1 <= pos) addTree(x * 2 + 1, pos, val);

update(x);

}

inline LL judge(LL mid)

{

LL ret = 0;

for (int i = 1; i <= n; i++)

{

if (num[i] < mid)

ret = ret + (num[i] - mid) / k + ((num[i] - mid) % k == 0 ? 0 : 1);

}

return ret;

}

inline void maxPossible()

{

if (T == 0) return ;

for (int i = 1; i <= n; i++)

{

if (num[i] < 0)

{

ff[i] = -1;

num[i] = -num[i];

}

else

{

ff[i] = 1;

}

build(1,1,n);

for (int rt = 1; rt <= T; rt++)

{

int minPos = tree[1].pos;

num[minPos] += k;

addTree(1,minPos,k);

}

for (int i = 1; i <= n; i++)

num[i] = num[i] * ff[i];

}

int main()

{

scanf("%d%I64d%I64d", &n, &T, &k);

for (int i = 1; i <= n; i++)

scanf("%I64d", &num[i]);

int flagF = 0, flagZ = 0;

for (int i = 1; i <= n; i++)

{

if (num[i] == 0) flagZ++;

if (num[i] < 0) flagF++;

}

//积只能为0

if (flagZ > T)

{

for (int i = 1; i <= n; i++)

{

if (num[i] == 0 && T > 0)

{

num[i] -= k;

T--;

}

if (i == n) printf("%I64d\n",num[i]); else printf("%I64d ",num[i]);

}

return 0;

}

if (flagZ > 0)

{

if (flagF & 1)

{

//0 -> 正数

for (int i = 1; i <= n; i++)

if (num[i] == 0)

{

num[i] += k;

T--;

}

else

{

//一个0 -> 正数

bool flag = true;

for (int i = 1;i <= n; i++)

if (num[i] == 0)

{

if (flag)

{

num[i] -= k;

flag = false;

}

else

{

num[i] += k;

}

T--;

}

maxPossible();

for (int i = 1; i <= n; i++)

if (i == n) printf("%I64d\n",num[i]); else printf("%I64d ",num[i]);

return 0;

}

if (flagF&1)

{

//负数乘积尽量大

maxPossible();

for (int i = 1; i <= n; i++)

if (i == n) printf("%I64d\n",num[i]); else printf("%I64d ",num[i]);

return 0;

}

//正数乘积尽量小

int maxFPos = -1,minZPos = -1;

for (int i = 1; i <= n; i++)

{

if (num[i] > 0)

{

if (minZPos == -1 || num[minZPos] > num[i]) minZPos = i;

}

else

{

if (maxFPos == -1 || num[maxFPos] < num[i] ) maxFPos = i;

}

if (maxFPos == -1) num[maxFPos=200001]=-1e9-1;

if (minZPos == -1) num[minZPos=200001]=1e9+1;

LL delta = min(-num[maxFPos], num[minZPos]);

if (delta / k + 1 <= T)

{

if (-num[maxFPos] > num[minZPos])

{

num[minZPos] -= (delta / k + 1) * k;

T -= delta / k + 1;

}

else

{

num[maxFPos] += (delta / k + 1) * k;

T -= delta / k + 1;

}

//负数乘积尽量大

maxPossible();

for (int i = 1; i <= n; i++)

if (i == n) printf("%I64d\n",num[i]); else printf("%I64d ",num[i]);

return 0;

}

else

{

if (-num[maxFPos] > num[minZPos])

{

num[minZPos] -= T * k;

}

else

{

num[maxFPos] += T * k;

}

for (int i = 1; i <= n; i++)

if (i == n) printf("%I64d\n",num[i]); else printf("%I64d ",num[i]);

return 0;

}

return 0;

}

WNJXYKの博客

喂你脚下有坑