Codeforces Round #350 (Div. 2)

A. Holidays

题意：一个礼拜有两天放假，那么n天最多和最少分别有多少天假呢？

题解：首先算最少的，就是n%7,如果余6的话则要+1。最多则是尽量让余下的天数为假期，如果余一天就加一天，余二就加两天，大于二依然只加两天，直到余六再加一天。

代码：

 1 /*A*/
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int n;
 8     while(scanf("%d",&n)!=EOF)
 9     {
10         int max=n/7*2;
11         int min=n/7*2;
12         int temp=n%7;
13         if(temp==1)
14             max++;
15         if(temp>=2)
16             max+=2;
17         if(temp==6)
18             min++;
19         printf("%d %d
",min,max);
20     }
21     return 0;
22  }

View Code

B. Game of Robots

题意：有n个机器人，编号唯一。做一个游戏，第一个机器人报一个编号，第二个机器人报第一和第二个编号，第三个机器人报第一第二第三个编号，依次类推，求报出的第k个编号是多少。

题解：根据1,2,3,4,5......这个等差数列就可以求。第i项代表第i个机器人报了i个编号。再又n*(n+1)/2我们可以求出当我们加到k时，报的第k个属于哪一项。

代码：

 1 /*D2*/
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 const int maxn=100000+10;
 6 long long a[maxn],b[maxn];
 7     long long n,k;
 8 long long check(long long p)
 9 {
10     long long temp=k;
11     for(long long i=0;i<n;i++)
12     {
13         long long d=b[i]-p*a[i];
14         if(d<0)
15             temp+=d;
16         if(temp<0)    break;
17     }
18     return temp;
19 }
20 long long find(long long l,long long r)
21 {
22     //printf("%I64d %I64d
",l,r);/**/
23     //if(l==104&&r==103)    return 1; 
24     if(l==r)
25         return l;
26     long long mid=(l+r)/2;
27     long long ret;
28     long long tt=check(mid);
29     if(tt==0)
30         ret=mid;
31     else if(tt<0)
32         ret=find(l,mid);
33     else
34     {
35         ret=mid;
36         long long temp=find(mid+1,r);
37         if(check(temp)>=0)
38             ret=temp;
39     }
40     return ret;
41 }
42 int main()
43 {
44 
45     scanf("%I64d%I64d",&n,&k);
46         for(int i=0;i<n;i++)
47             scanf("%I64d",&a[i]);
48         for(int i=0;i<n;i++)
49             scanf("%I64d",&b[i]);
50         long long ans=find(0,2000000000+100);
51         printf("%I64d
",ans);    
52     return 0;
53 }

View Code

C. Cinema

题意:有n个人，他们懂不同的语言，现在要去看一场电影，电影的声音是一种语言，字幕是一种语言，如果一个人会的语言和声音的语言一样，那么他会很满意，如果字幕的语言和他会的一样那么他感觉一般，现在问看哪一场电影可以让最多的人很满意，如果满意的人一样的话则比较感觉一般的人数。

题解：用map来存储每个语言会的人数，然后在找到每场电影中满意的人数和感觉一般的人数，最后sort一下。

代码：

 1 /*C*/
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<map>
 5 #include<cstring>
 6 using namespace std;
 7 
 8 const int maxn=200000+100;
 9 struct data{
10     int id;
11     int b;
12     int c;
13 };
14     struct data mo[maxn];
15 bool cmp(struct data x,struct data y)
16 {
17     if(x.b!=y.b)
18         return x.b>y.b;
19     else
20         return x.c>y.c;
21 }
22 int main()
23 {
24     int n;
25     map<int,int> a;
26     scanf("%d",&n);
27     int temp;
28     for(int i=0;i<n;i++)
29     {
30         scanf("%d",&temp);
31         a[temp]++;
32     }
33     int m;
34     scanf("%d",&m);
35     for(int i=0;i<m;i++)
36     {
37         scanf("%d",&temp);
38         mo[i].b=a[temp];
39         mo[i].id=i;
40     }
41     for(int i=0;i<m;i++)
42     {
43         scanf("%d",&temp);
44         mo[i].c=a[temp];
45     } 
46     sort(mo,mo+m,cmp);
47     printf("%d
",mo[0].id+1);
48     return 0;
49  }

View Code

D2. Magic Powder - 2题意：用已有的材料和魔法材料来做蛋糕，魔法材料可以抵用任何一种材料。问最多可以做多少个蛋糕。

题解：二分答案，贪心来判断当前的mid是不是可行的。

代码：

 1 /*D2*/
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 const int maxn=100000+10;
 6 long long a[maxn],b[maxn];
 7     long long n,k;
 8 long long check(long long p)
 9 {
10     long long temp=k;
11     for(long long i=0;i<n;i++)
12     {
13         long long d=b[i]-p*a[i];
14         if(d<0)
15             temp+=d;
16         if(temp<0)    break;
17     }
18     return temp;
19 }
20 long long find(long long l,long long r)
21 {
22     //printf("%I64d %I64d
",l,r);/**/
23     //if(l==104&&r==103)    return 1; 
24     if(l==r)
25         return l;
26     long long mid=(l+r)/2;
27     long long ret;
28     long long tt=check(mid);
29     if(tt==0)
30         ret=mid;
31     else if(tt<0)
32         ret=find(l,mid);
33     else
34     {
35         ret=mid;
36         long long temp=find(mid+1,r);
37         if(check(temp)>=0)
38             ret=temp;
39     }
40     return ret;
41 }
42 int main()
43 {
44 
45     scanf("%I64d%I64d",&n,&k);
46         for(int i=0;i<n;i++)
47             scanf("%I64d",&a[i]);
48         for(int i=0;i<n;i++)
49             scanf("%I64d",&b[i]);
50         long long ans=find(0,2000000000+100);
51         printf("%I64d
",ans);    
52     return 0;
53 }

View Code

代码2：很好的二分写法，学习一下

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 2e5+5;
 4 const int inf = ~0u>>1;
 5 typedef long long ll;
 6 ll a[N], b[N], p[N];
 7 bool ok(ll x, ll n, ll k){
 8     for(int i = 1; i <= n; ++i){
 9         if(p[i] < x){
10             ll tmp = a[i]-b[i]%a[i] + (x-p[i]-1)*a[i];
11             if(tmp > k) return 0;
12             else k -= tmp;
13         }
14     }
15     return 1;
16 }
17 int main(){
18     ll n, k;
19     scanf("%lld%lld", &n, &k);
20     for(int i = 1; i <
21     = n; ++i) scanf("%lld", a+i);
22     for(int i = 1; i <= n; ++i) scanf("%lld", b+i);
23     for(int i = 1; i <= n; ++i) p[i] = b[i]/a[i];
24     ll l = 0, r = inf, ans = 0;
25     while(l <= r){
26         ll mid = (l+r) >> 1;
27         if(ok(mid, n, k)) l = mid+1, ans = mid;
28         else r = mid-1;
29     }
30     printf("%lld
", ans);
31 }

View Code