Codeforces Round 350 (Div. 2) ABCD1D2

https://codeforces.com/contest/670

A. Holidays

题目大意：

给定n天，求出可以休息的最大小时间和最大时间。

input
14
output
4 4

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN;
const LL N=2e5+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
LL a[N];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        if(n<=2) cout<<"0 "<<n<<endl;
        else
        {
            LL sum1=n/7*2+max((LL)0,n%7-5);
            LL sum2=2;
            n-=2;
            sum2+=n/7*2+max((LL)0,n%7-5);
            cout<<sum1<<" "<<sum2<<endl;
        }
    }
    return 0;
}

B. Game of Robots

题目大意：

一个人报名字会把前面所有人的名字也全都报一遍，

问我们在n个人中喊出的第m个名字是谁？

input 
4 5
10 4 18 3
output 
4

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN;
const LL N=2e5+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
LL a[N],b[N];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)
    {
        LL n,m;
        cin>>n>>m;
        b[0]=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            b[i]=b[i-1]+i;
        }
        LL idx=lower_bound(b+1,b+1+n,m)-b-1;
        LL op=m-b[idx];
        cout<<a[op]<<endl;
    }
    return 0;
}

C. Cinema

题目大意：

n个人一起看电影，每个人都有自己认识的语言；

m部电影，每一部电影都有值ai，bi，

ai值和看电影的人符合，则特别满意度上升；bi值和看电影的人符合，则满意度上升。

问我们选哪一部电影能够让特别满意度最大？

input 
3
2 3 2
2
3 2
2 3
output 
2

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN;
const LL N=2e5+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
struct node
{
    LL l=0,r=0;
    LL idx;
}a[N];
bool cmp(node xx,node yy)
{
    if(xx.l!=yy.l) return xx.l>yy.l;
    else return xx.r>yy.r;
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        map<LL,LL> know;
        for(int i=1;i<=n;i++)
        {
            LL x;
            cin>>x;
            know[x]++;
        }
        LL m;
        cin>>m;
        for(int i=1;i<=m;i++)
        {
            LL x;
            cin>>x;
            a[i].l+=know[x];
        }
        for(int i=1;i<=m;i++)
        {
            LL x;
            cin>>x;
            a[i].r+=know[x];
            a[i].idx=i;
        }
        sort(a+1,a+1+m,cmp);
        /*
        for(int i=1;i<=n;i++)
        {
            cout<<a[i].idx<<" "<<a[i].l<<" "<<a[i].r<<endl;
        }
        */
        cout<<a[1].idx<<endl;
    }
    return 0;
}

D1. Magic Powder - 1

题目大意：

做一种食物需要n种原料，每种原料需要ai个，

我们现有n种原料bi个，还有m个可随机作为原料的替代。

问我们可以做出这种食物的最大数量是多少？

input
3 1
2 1 4
11 3 16
output
4

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN;
const LL N=2e5+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
LL a[N],b[N];
LL ans=0;
LL n,m;
bool check(LL x)
{
    LL res=0;
    for(int i=1;i<=n;i++)
    {
        if(x*a[i]<=b[i]) ;
        else res+=(x*a[i]-b[i]);
        if(res>m) return false;
    }
    if(res<=m) return true;
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>m;
        LL l=MAXN,r=1e9;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        for(int i=1;i<=n;i++)
        {
            cin>>b[i];
            l=min(l,b[i]/a[i]);
        }
        while(l<=r)
        {
            LL mid=(l+r)/2;
            if(check(mid))
            {
                l=mid+1;
                ans=mid;
            }
            else r=mid-1;
        }
        cout<<ans<<endl;
    }
    return 0;
}

D2. Magic Powder - 2

题目大意：

语义和D1一样，变化在D2数据范围增大。

input 
1 1000000000
1
1000000000
output 
2000000000

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN;
const LL N=2e5+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
int a[N],b[N],ans=0,n,m;
bool check(int x)
{
    LL res=0;
    for(int i=1;i<=n;i++)
    {
        LL flag=(LL)a[i]*x;
        if(flag>b[i])
            res+=(flag-b[i]);
        if(res>m) return false;
    }
    if(res<=m) return true;
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>m;
        LL l=0,r=2e9+1;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        for(int i=1;i<=n;i++)
        {
            cin>>b[i];
        }
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(check(mid))
            {
                l=mid+1;
                ans=mid;
            }
            else r=mid-1;
        }
        cout<<ans<<endl;
    }
    return 0;
}

还是之前的div2好写呀