首页 > 代码库 > 【uva 1614】Hell on the Markets（算法效率--贪心）
【uva 1614】Hell on the Markets（算法效率--贪心）
题意：有一个长度为N的序列A，满足1≤Ai≤i，每个数的正负号不知。请输出一种正负号的情况，使得所有数的和为0。(N≤100000)
解法：（我本来只想静静地继续做一个口胡选手...←_← 但是因为这题的贪心实在是太厉害了！我就单看，就盯了题解半小时以上...而代码又那么短，我就打了代码了...其实我又不太理解为什么一定要排序。）
贪心部分的理论依据：前i个数可以凑出1～sum[i]的所有整数。
证明：第二类数学归纳，n=1时成立，假设n=k之前所有项都成立，当n=k+1时。sum[k+1]=sum[k]+a[k+1]。
只需证明能凑出sum[k]+1~sum[k+1]间的整数即可。设1≤p≤a[k+1]，sum[k]+p=sum[k]+a[k+1]-(a[k+1]-p)。
因为1≤a[i]≤i，易得sum[k]≥k,a[k+1]-p≤k。又因为已知前k个数可以凑出1~sum[k]，所以一定可以凑出a[k+1]-p。
所以只需从之前凑出sum[k]里面剪掉凑出a[k+1]-p的数就可以凑出sum[k]+p。所以从1~sum[k+1]都可以凑出。
实现就是输入时存一下sum，若为奇数就无解，否则再排个序，从大到小扫一遍，选凑成和为sum/2的数的符号为+，其余为-。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6 7 const int N=100010; 8 struct node{int x,id;}a[N]; 9 int b[N],ans[N];10 11 bool cmp(node x,node y) {return x.x>y.x;}12 int main()13 {14 int n;15 long long sum;//不能用int16 while (~scanf("%d",&n))17 {18 sum=0;19 for (int i=1;i<=n;i++)20 {21 scanf("%d",&a[i].x);22 a[i].id=i, sum+=a[i].x;23 }24 if (sum%2) {printf("No\n");continue;}25 printf("Yes\n");26 sum/=2;27 sort(a+1,a+1+n,cmp);28 for (int i=1;i<=n;i++)29 {30 if (a[i].x<=sum) ans[a[i].id]=1,sum-=a[i].x;31 else ans[a[i].id]=-1;32 }33 printf("%d",ans[1]);34 for (int i=2;i<=n;i++)35 printf(" %d",ans[i]);36 printf("\n");37 }38 return 0;39 }
【uva 1614】Hell on the Markets（算法效率--贪心）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。