Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 说一下贪心法的策略

Posted by SlgCoder at 2016-04-20 10:38:04 on Problem 2718
```两个数

//input A[10], N
int solve2()
{
if (N == 2) {
return A[1]-A[0];
} else if (N % 2) {
if (A[0] == 0) {
int tmp = A[1];
A[1] = A[0];
A[0] = tmp;
}
A[1] += A[0]*10;
int ans = 0;
for (int i = 1; i <= N/2; i++) {
ans *= 10;
ans += (A[i]-A[N-i]);
}
return ans;
} else {
int ival[10];					//interval
int ST = 0;					//start
if (A[ST] == 0)
ST++;
for (int i = ST; i+1 < N; i++)
ival[i] = A[i+1]-A[i];
int min1 = INF, pos1, min2 = INF, pos2;
for (int i = ST; i < N/2; i++) {
if (ival[i] <= min1) {
min1 = ival[i];
pos1 = i;
}
}
for (int i = N-2; i >= (N/2)-1; i--) {
if (ival[i] <= min2) {
min2 = ival[i];
pos2 = i;
}
}
int A2[10];
for (int i = 0; i < N; i++)
A2[i] = A[i];

int ans1 = 0;
int tmp1 = A[pos1+1], tmp2 = A[pos1];
for (int i = pos1; i > 0; i--)
A[i] = A[i-1];
for (int i = pos1+1; i < N-1; i++)
A[i] = A[i+1];
A[0] = tmp1;
A[N-1] = tmp2;
for (int i = 0; i < N/2; i++) {
ans1 *= 10;
ans1 += (A[i]-A[N-1-i]);
}

int ans2 = 0;
tmp1 = A2[pos2+1], tmp2 = A2[pos2];
for (int i = pos2; i > 0; i--)
A2[i] = A2[i-1];
for (int i = pos2+1; i < N-1; i++)
A2[i] = A2[i+1];
A2[0] = tmp1;
A2[N-1] = tmp2;
for (int i = 0; i < N/2; i++) {
ans2 *= 10;
ans2 += (A2[i]-A2[N-1-i]);
}
return ((ans1 > ans2) ? ans2 : ans1);
}
}```

Followed by: