Educational Codeforces Round 21 题解

比赛链接:http://codeforces.com/contest/808

A Lucky Year

题意

定义一个幸运数字:有且只含有一个非零数字。给出一个数n,求这个增加多少个数以后才能够成为一个幸运数字

题解

数据范围比较小,求出位数,得到最高位大1后面全是0的数,拿这个数去减原来的数就行了

代码

1
2
3
4
5
6
7
void solve()
{
int n,i;
scanf("%d",&n);
for(i=1;n/(i*10);i*=10);
printf("%d",n/i*i+i-n);
}

B Average Sleep Time

题意

给出一个包含n个元素的序列,表示每天的睡眠时间,同时给出一个k,表示相邻k天是一个周期,总共有n-k+1个周期,求周期平均睡眠时间

题解

根据公式直接进行求解,输出的时候多输出几位,保证精度

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve()
{
int n,k,r;
double ans;
while(cin>>n>>k)
{
double tmp=0;
ans=0;
int weeks=n-k+1;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<k;i++)
tmp+=a[i];
for(int i=k-1;i<n;i++)
{
ans+=tmp/weeks;
tmp+=a[i+1];
tmp-=a[i-k+1];
}
printf("%.12lf\n",ans);
}
}

C Tea Party

题意

给出n个人的杯子的容量,以及你所含有的水的量,要求给n个人倒茶,必须满足以下条件:1.每个人的杯子必须至少倒一半的茶 2.每个人的杯子中含有的茶的量是一个整数 3.所有的茶都要倒完 4.所有人都要满意(不存在有的人杯子大但是茶少的情况)
判断是否存在满足上述条件的倒茶方法

题解

  • 首先判断能够给每个人至少倒一半的茶
  • 根据总量推算出倒茶的比例,再按照杯子的容量进行排序,按照比例向下取整进倒茶,多出来的部分分给杯子容量最大的人,以此类推
  • 注意取整操作,以及满足至少倒一半的操作

代码

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
const int maxn=105;
const int maxm=100005;
int ans[maxn];
struct node
{
int v,u,id;
}a[maxn];
bool Cmp1(const node &a,const node &b)
{
return a.v<b.v;
}
bool Cmp2(const node &a,const node &b)
{
return a.id<b.id;
}
void solve()
{
int n,w;
int sum;
while(cin>>n>>w)
{
sum=0;
for(int i=1;i<=n;i++)
{
cin>>a[i].v;
a[i].id=i;
sum+=a[i].v;
}
double rate=1.0*w/sum;
if(rate<0.5)
{
cout<<"-1"<<endl;
continue;
}
int last=w,tmp;
bool endflag=0;
sort(a+1,a+n+1,Cmp1);
for(int i=1;i<=n;i++)
{
tmp=floor(a[i].v*rate);
if(2*tmp<a[i].v) tmp++; //防止在一半以下
a[i].u=tmp;
last-=a[i].u;
if(last<0) endflag=1;
}
if(endflag)
{
cout<<"-1"<<endl;
continue;
}
for(int i=n;last>0;i--)
{
tmp=a[i].v-a[i].u;
if(last>=tmp)
{
last-=tmp;
a[i].u=a[i].v;
}
else
{
a[i].u+=last;
last=0;
}
}
sort(a+1,a+n+1,Cmp2);
for(int i=1;i<=n;i++)
cout<<a[i].u<<" ";
cout<<endl;
}
}

D Array Division

题意

给出一个序列,允许将两个数相互交换一次或者不交换,问是否能够将两个数分成相等的两个部分

题解

思路一

先求出前缀和,再用Set维护两个集合,前面的集合/后面的集合,从1开始将序列分成两半,判断两者差的一半是否在集合中能够找到

思路二

使用二分,求出前缀和,从前向后枚举交换的元素,用二分向前向后查找是否能够找到交换以后形成总数的一半的部分

代码

思路一

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
const int maxn=100005;
const int maxm=100005;
int a[maxn],n;
ll s[maxn],tot;
void solve()
{
while(scanf("%d",&n)!=EOF)
{
tot=0;
s[0]=0;
multiset<int> s1,s2;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
s2.insert(a[i]);
tot+=a[i];
s[i]=s[i-1]+a[i];
}
if(tot&1)
{
printf("NO\n");
continue;
}
ll A,B,tmp;
bool endflag=1;
for(int i=1;i<=n;i++)
{
A=s[i],B=s[n]-s[i];
if(A==B)
{
printf("YES\n");
endflag=0;
break;
}
tmp=A-B;
s2.erase(s2.find(a[i]));
s1.insert(a[i]);
if(tmp>0 && tmp%2==0 && tmp<=MAXX) //差值为偶数
{
if(s1.find(tmp/2)!=s1.end())
{
printf("YES\n");
endflag=0;
break;
}
}
if(tmp<0 && tmp%2==0 && tmp>=-MAXX)
{
if(s2.find(-tmp/2)!=s2.end())
{
printf("YES\n");
endflag=0;
break;
}
}
}
if(endflag) printf("NO\n");
}
}

思路二

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
46
47
48
49
50
51
52
53
54
55
56
const int maxn=100010;
const int maxm=100005;
int a[maxn];
ll s[maxn];
int main() {
int n;
scanf("%d",&n);
ll tot=0;
for(int i=1;i<=n;++i) {
scanf("%d", &a[i]);
tot += a[i];
}
if(tot%2!=0 || n==1){
printf("NO\n");
return 0;
}
tot/=2;
s[0]=a[0];
for(int i=1;i<=n+1;++i){
s[i]=s[i-1]+a[i];
}
for(int i=1;i<=n;++i){
if(a[i]==tot){
printf("YES\n");
return 0;
}
//正二分
int l=0,r=i-1;
while(l<=r){
int mid=(l+r)>>1;
ll temp=s[mid]+a[i];
if(temp==tot){
printf("YES\n");
return 0;
}
if(temp<tot) l=mid+1;
else r=mid-1;
}
l=i+1,r=n;
while(l<=r){
int mid=(l+r)>>1;
ll temp=s[n]-s[mid]+a[i];
if(temp==tot){
printf("YES\n");
return 0;
}
if(temp<tot) r=mid-1;
else l=mid+1;
}
}
printf("NO\n");
return 0;
}