Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题目链接 题意:有1E9个礼物，第i个礼物价钱是i,然后现在已经有n个不重复的礼物，a[i],m元钱，想尽可能多得买不同种类的礼物，还能买多少个。 思路：先不考虑已经买的，从1连续买到k,然后考虑子啊这个区间内已经买的，等于实际上没有花钱。 反正就是暴力搞啊搞啊。。我也不知道怎么搞。。 结果最后。。方案数为0的时候。。。最后一个答案我是单独输出的。。忘了判断了。。。所以会输出两个0.宝宝心里苦啊。。。。。。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年03月31日 星期四 00时00分03秒
4File Name :code/cf/#346/C.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=3E5+7;
34LL n,m;
35LL a[N];
36LL sum[N];
37set<LL>se;
38LL ans[N];
39bool vis[N];
40int main()
41{
42 #ifndef ONLINE_JUDGE
43 freopen("code/in.txt","r",stdin);
44 #endif
45 ms(vis,false);
46// ios::sync_with_stdio(false); //注意这题可能会爆long long
47 cin>>n>>m;
48 sum[0] = 0LL;
49 for ( int i = 1 ; i <= n ;i++)
50 {
51 cin>>a[i];
52 sum[i] = sum[i-1] + a[i];
53 se.insert(a[i]);
54 }
55
56 sort(a+1,a+n+1);
57
58 LL k;
59 for ( LL i =1 ; ; i++)
60 {
61 LL tmp =i*(i+1)/2;
62 if (tmp>m)
63 {
64 k = i-1;
65 break;
66 }
67 vis[i] = true;
68 }
69 LL cost = k*(k+1)/2;
70// cout<<"k:"<<k<<endl;
71 for ( int i = 1 ; i <= n ; i++)
72 {
73 if (a[i]<=k)
74 {
75 cost -= a[i];
76 vis[a[i]] = false;
77 }
78 else
79 break;
80 }
81
82// cout<<"cost:"<<cost<<endl;
83// LL res = m-cost;
84// cout<<"res:"<<res<<endl;
85
86
87 for ( LL i = k; ; i++)
88 {
89 if (se.count(i+1)) continue;
90 cost = cost + i + 1;
91 if (cost>m)
92 {
93 k = i;
94 break;
95 }
96 vis[i+1] =true;
97
98 }
99
100
101
102
103
104
105 ms(ans,0LL);
106// cout<<"k:"<<k<<endl;
107 int cnt = 0 ;
108 for ( int i = 1 ; i <= k ; i++)
109 {
110 if (vis[i])
111 {
112 cnt++;
113 ans[cnt] = i;
114 }
115 }
116 cout<<cnt<<endl;
117 for ( int i = 1 ; i < cnt ; i++) cout<<ans[i]<<" ";
118 if (cnt!=0)
119 cout<<ans[cnt];
120
121
122
123
124
125
126 #ifndef ONLINE_JUDGE
127 fclose(stdin);
128 #endif
129 return 0;
130}