A. Toda 2
2 seconds
512 megabytes
standard input
standard output
A group of n friends enjoys playing popular video game Toda 2. There is a rating system describing skill level of each player, initially the rating of the i-th friend is ri.
The friends decided to take part in the championship as a team. But they should have equal ratings to be allowed to compose a single team consisting of all n friends. So the friends are faced with the problem: how to make all their ratings equal.
One way to change ratings is to willingly lose in some matches. Friends can form a party consisting of two to five (but not more than n) friends and play a match in the game. When the party loses, the rating of each of its members decreases by 1. A rating can't become negative, so ri = 0 doesn't change after losing.
The friends can take part in multiple matches, each time making a party from any subset of friends (but remember about constraints on party size: from 2 to 5 members).
The friends want to make their ratings equal but as high as possible.
Help the friends develop a strategy of losing the matches so that all their ratings become equal and the resulting rating is maximum possible.
The first line contains a single integer n (2 ≤ n ≤ 100) — the number of friends.
The second line contains n non-negative integers r1, r2, ..., rn (0 ≤ ri ≤ 100), where ri is the initial rating of the i-th friend.
In the first line, print a single integer R — the final rating of each of the friends.
In the second line, print integer t — the number of matches the friends have to play. Each of the following t lines should contain ncharacters '0' or '1', where the j-th character of the i-th line is equal to:
- '0', if friend j should not play in match i,
- '1', if friend j should play in match i.
Each line should contain between two and five characters '1', inclusive.
The value t should not exceed 104, it is guaranteed that such solution exists.
Remember that you shouldn't minimize the value t, but you should maximize R. If there are multiple solutions, print any of them.
思路：贪心；
因为可以同时操作2-5个，那么我们只要讨论时操作2个或三个就行了因为2，3能组成其他数，然后每次分类，当当前的数有偶数个，那么每次操作2个，当前为1的时候也操作2个，否则操作3个，并且选出的是最大的，这个用优先队列维护。
1 #include<stdio.h>
2 #include<algorithm>
3 #include<stdlib.h>
4 #include<queue>
5 #include<string.h>
6 #include<iostream>
7 #include<math.h>
8 using namespace std;
9 typedef struct node
10 {
11 int id;
12 int cost;
13 bool operator<(const node&cx)const
14 {
15 return cx.cost > cost;
16 }
17 } ss;
18 int ans[1000];
19 int ab[10005][105];
20 priority_queue<ss>que;
21 int flag[1005];
22 int main(void)
23 {
24 int n;
25 scanf("%d",&n);
26 int i,j;
27 for(i = 0; i < n; i++)
28 {
29 scanf("%d",&ans[i]);
30 }
31 memset(ab,0,sizeof(ab));
32 while(!que.empty())
33 que.pop();
34 memset(flag,0,sizeof(flag));
35 int cn = 0;
36 for(i = 0; i < n; i++)
37 {
38 if(!flag[ans[i]])
39 {
40 cn++;
41 }
42 flag[ans[i]]++;
43 ss ak;
44 ak.cost = ans[i];
45 ak.id = i;
46 que.push(ak);
47 }
48 int cnt = 0;
49 while(cn>1)
50 {
51 ss a = que.top();
52 que.pop();
53 ss b = que.top();
54 que.pop();
55 if(a.cost!=b.cost)
56 {
57 if(a.cost>0)
58 {
59 flag[a.cost]--;
60 if(flag[a.cost]==0)cn--;
61 if(flag[a.cost-1]==0)cn++;
62 a.cost--;
63 flag[a.cost]++;
64 }
65 if(b.cost>0)
66 {
67 flag[b.cost]--;
68 if(flag[b.cost]==0)cn--;
69 if(flag[b.cost-1]==0)cn++;
70 b.cost--;
71 flag[b.cost]++;
72 }
73 ab[cnt][a.id]++;
74 ab[cnt][b.id]++;
75 }
76 else if(flag[a.cost]%2==0)
77 {
78 if(a.cost>0)
79 {
80 flag[a.cost]--;
81 if(flag[a.cost]==0)cn--;
82 if(flag[a.cost-1]==0)cn++;
83 a.cost--;
84 flag[a.cost]++;
85 }
86 if(b.cost>0)
87 {
88 flag[b.cost]--;
89 if(flag[b.cost]==0)cn--;
90 if(flag[b.cost-1]==0)cn++;
91 b.cost--;
92 flag[b.cost]++;
93 }
94 ab[cnt][a.id]++;
95 ab[cnt][b.id]++;
96 }
97 else
98 {
99 ss c = que.top();
100 que.pop();
101 if(a.cost>0)
102 {
103 flag[a.cost]--;
104 if(flag[a.cost]==0)cn--;
105 if(flag[a.cost-1]==0)cn++;
106 a.cost--;
107 flag[a.cost]++;
108 }
109 if(b.cost>0)
110 {
111 flag[b.cost]--;
112 if(flag[b.cost]==0)cn--;
113 if(flag[b.cost-1]==0)cn++;
114 b.cost--;
115 flag[b.cost]++;
116 }
117 if(c.cost>0)
118 {
119 flag[c.cost]--;
120 if(flag[c.cost]==0)cn--;
121 if(flag[c.cost-1]==0)cn++;
122 c.cost--;
123 flag[c.cost]++;
124 }ab[cnt][c.id]++;
125 ab[cnt][a.id]++;
126 ab[cnt][b.id]++;
127 que.push(c);
128 }
129 cnt++;
130 que.push(a);
131 que.push(b);
132 }
133 int x = que.top().cost;
134 printf("%d\n",x);
135 printf("%d\n",cnt);
136 for(i = 0;i < cnt;i++)
137 {
138 for(j = 0;j < n;j++)
139 {
140 if(j == 0)
141 printf("%d",ab[i][j]);
142 else printf("%d",ab[i][j]);
143 }
144 printf("\n");
145 }
146 return 0;
147 }
最新文章
- 程序设计入门——C语言 第7周编程练习 1多项式加法（5分）
- DIV+CSS：Margin和Padding属性[转载]
- 1106 c程序的推导过程
- 3.工厂方法模式(Factory Method)
- ie6双边距解决
- kickstrat
- C# 使用 AutoResetEvent 或 ManualResetEvent 同步两个线程
- GCC内联汇编入门
- C++在设计和使用智能指针
- iOS 开发者旅途中的指南针 - LLDB 调试技术
- 201521145048《java程序设计》第10周学习总结
- LInkedHashMap实现最近被使用（LRU）缓存
- python 2 和 python 3 的区别
- 实用的sublime插件集合 – sublime推荐必备插件
- 仿B站项目——(1)计划，前端工程
- Nodejs使用多个分隔符分隔字符串
- MySQL中的xtrabackup的原理解析
- 使用OleDB组件连接和访问Oracle数据库
- JS判断输入值为正整数
- RabbitMQ入门_03_推拉模式