UVA - 1614 Hell on the Markets(奇怪的股市)(贪心)

时间:2021-08-19 09:34:48

题意:输入一个长度为n(n<=100000)的序列a,满足1<=ai<=i,要求确定每个数的正负号,使得所有数的总和为0。

分析:

1、若总和为0,则未加符号之前,所有数之和必为偶数。

2、现在考虑是否有一部分数的和能等于sum/2。

方法:cnt[i]为数字i的个数,(当前的sum)/i为需要凑出当前的sum需要有多少个整数i,两者的最小值就是实际用的i的个数,即use[i]。(use[i]为0的情况:1、枚举过程中,不存在i这个数。2、i大于当前的sum,所以凑出sum/2不能使用i)

若最终sum==0,则表示序列中的一部分数能凑出sum/2。这部分数就是所有的不为0的use[i]。

#pragma comment(linker, "/STACK:102400000, 102400000")
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#define Min(a, b) ((a < b) ? a : b)
#define Max(a, b) ((a < b) ? b : a)
const double eps = 1e-8;
inline int dcmp(double a, double b) {
if(fabs(a - b) < eps) return 0;
return a < b ? -1 : 1;
}
typedef long long LL;
typedef unsigned long long ULL;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const int MAXN = 100000 + 10;
const int MAXT = 10000 + 10;
using namespace std;
int a[MAXN];
int cnt[MAXN];
int use[MAXN];
void init(){
memset(a, 0, sizeof a);
memset(cnt, 0, sizeof cnt);
memset(use, 0, sizeof use);
}
int main(){
int n;
while(scanf("%d", &n) == 1){
init();
LL sum = 0;
int ma = 0;
for(int i = 1; i <= n; ++i){
scanf("%d", &a[i]);
ma = Max(ma, a[i]);
sum += a[i];
++cnt[a[i]];
}
if(sum & 1){
printf("No\n");
continue;
}
sum /= 2;
bool flag = false;
for(int i = ma; i >= 1; --i){
use[i] = Min(cnt[i], sum / i);
sum -= use[i] * i;
if(sum == 0){
flag = true;
break;
}
}
if(!flag){
printf("No\n");
continue;
}
printf("Yes\n");
for(int i = 1; i <= n; ++i){
if(i != 1) printf(" ");
if(use[a[i]]){
printf("1");
--use[a[i]];
}
else printf("-1");
}
printf("\n");
}
return 0;
}