点击阅读更多查看文章内容
UVA1614 Hell on the Markets
题目传送门
这道题主要考察的数学推理能力，一点思路都没有，大佬的分析都看了好久。
这道题主要用到的是数学归纳法，用sum[i]表示前i项的和，从1到sum[i]之间的任意一个数，都可以用a[1]到a[i]中的若干个数表示出来。
具体证明方法以及选数的方法可以看下面这篇文章
https://blog.csdn.net/weixin_30820151/article/details/101380416
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 1e5 + 10;
int A[MAXN];
int fh[MAXN];
int main()
{
int n;
while (cin >> n)
{
long long sum = 0;
memset(fh, 0, sizeof(fh));
memset(A, 0, sizeof(A));
for (int i = 0; i < n; i++)
{
cin >> A[i];
sum += A[i];
}
if (sum & 1)
{
cout << "No" << endl;
continue;
}
cout << "Yes" << endl;
sum /= 2;
for (int j =n-1; j >= 0; j--)
{
if (sum - A[j] >= 0)
{
sum -= A[j];
fh[j] = 1;
}
else
{
fh[j] = -1;
}
}
for (int i = 0; i < n; i++)
{
cout << fh[i] << " ";
}
cout << endl;
}
}
|
