DQS DQS

HIT Summer Training Day1 贪心|二分|三分

in 贪心,二分&&三分,算法,模拟赛read (183) 文章转载请注明来源!

A~E是贪心,F~J是二分。


A : codeforces - 651A

很简单,注意特判电量都为1时答案是0。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    if(a == 1 && b == 1) {puts("0"); return 0;}
    int ans = 0;
    if(a > b) swap(a,b);
    while(a > 0 && b > 0)
    {
        ans ++;
        a ++; b -= 2;
        if(a > b) swap(a,b);
    }
    printf("%d",ans);
    return 0;
}


B : codeforces - 723C

题意很繁琐…

大概意思是,有许多乐队,n首歌,要把n首歌分给许多乐队唱,已经有了每首歌对应谁唱的名单。其中前m个乐队是被喜欢的,要求前m个乐队中唱歌最少的乐队唱歌尽量多,在满足这个条件的前提下要求修改最少次名单。求唱歌最少的乐队唱歌尽量多的答案,以及修改次数,以及最终名单。

需要注意一些大于m的乐队可以不用管。我就被题意杀了…………


#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 2010;

int a[SZ],t[SZ];

queue<int> q[SZ];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int ans1 = n / m,ans2 = 0;
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d",&a[i]);
        if(a[i] <= m) q[a[i]].push(i);
    }
    for(int x = 1;x <= m;x ++)
        for(int y = 1;y <= m;y ++)
            while(q[x].size() < ans1 && q[y].size() > ans1)
            {
                int id = q[y].front(); q[y].pop();
                q[x].push(id); a[id] = x; ans2 ++;
            }    
    for(int i = 1;i <= n;i ++)
    {
        int x = a[i];
        if(x > m)
        {
            bool flag = 0;
            for(int y = 1;y <= m;y ++)
                if(q[y].size() < ans1)
                {
                    q[y].push(i),a[i] = y,flag = 1,ans2 ++;
                    break;
                }
        }
    }

    printf("%d %d\n",ans1,ans2);
    for(int i = 1;i <= n;i ++)
        printf("%d ",a[i]);
    return 0;
}


C : poj1700

有n个人过河,其中第i个人过河时间是$a_i$,有一条小船只能载两个人,船划到对岸需要有人划回来。问所有人过河的最小时间。

对于$n<=3$的情况,进行特判。

对于$n>=4$的情况,不妨先考虑$n=4$。我们按过河时间递增顺序记四人为a,b,c,d。

一共有两种情况:ab先过,a回来,cd再过,b回来(时间差距不大);

或者是ab先过,a回来,a带c过,a回来,a带d过,a回来(时间差距较大)。

我们发现ab没有动,cd到了对岸。并且可以发现只有这两种策略,取优即可。

所以对于$n>4$时,ab为最快的两人,cd为最慢的两人,这样每次计算都会让n减小2,这样就可以递归计算了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 3010;

int t[SZ];

int get1(int a,int b,int c,int d)
{
    return b + a + d + b;
}

int get2(int a,int b,int c,int d)
{
    return c + a + d + a;
}

int dfs(int l,int r)
{
    int len = r - l + 1;
    if(len <= 2) return t[r];
    if(len == 3) return t[l] + t[r] + t[r - 1];
    int a = t[l],b = t[l + 1],c = t[r - 1],d = t[r];
    int t1 = get1(a,b,c,d);
    int t2 = get2(a,b,c,d);
    return min(t1,t2) + dfs(l,r - 2);
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T --)
    {
        int n;
        scanf("%d",&n);
        for(int i = 1;i <= n;i ++)
            scanf("%d",&t[i]);
        sort(t + 1,t + 1 + n);
        printf("%d\n",dfs(1,n));
    }

    return 0;
}

D : hdu1789

经典的用堆贪心。

每次找到之前价值不大的替换掉即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 3010;

struct haha
{
    int a,b;
}l[SZ];

bool cmp(haha a,haha b)
{
    if(a.a != b.a)
        return a.a < b.a;
    return a.b > b.b;
}


priority_queue<int> q;

int main()
{
    int T;
    scanf("%d",&T);
    while(T --)
    {
        while(q.size()) q.pop();
        int n,sum = 0;
        scanf("%d",&n);
        for(int i = 1;i <= n;i ++)
            scanf("%d",&l[i].a);
        for(int i = 1;i <= n;i ++)
            scanf("%d",&l[i].b),sum += l[i].b;
        sort(l + 1,l + 1 + n,cmp);
        int ans = 0;
        for(int i = 1,T = 1;i <= n;i ++)
        {
            if(l[i].a >= T)
                ans += l[i].b,q.push(-l[i].b),T ++;
            else
            {
                int x = -q.top();
                if(x < l[i].b)
                    q.pop(),ans -= x,ans += l[i].b,q.push(-l[i].b);
            }
        }
        printf("%d\n",sum - ans);
    }

    return 0;
}


E :hdu4864

机器和任务都为<x,y>二元组,要求机器的x和y都要大于等于任务的,这个任务才能在这个机器上运行。产生的价值是任务的$x500+y2$,求使执行的任务数量最大,其次使价值最大。

对于每个任务,找到刚好能运行它的机器,计算即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;

typedef long long LL;
const int SZ = 100010;

struct haha
{
    int a,b;
}mac[SZ],tsk[SZ];

bool operator <(haha a,haha b)
{
    if(a.a != b.a) return a.a < b.a;
    return a.b < b.b;
}

bool cmp(haha a,haha b)
{
    return b < a;
}

int pos[110];

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i = 1;i <= n;i ++)
            scanf("%d%d",&mac[i].a,&mac[i].b);
        for(int i = 1;i <= m;i ++)
            scanf("%d%d",&tsk[i].a,&tsk[i].b);
        sort(tsk + 1,tsk + 1 + m,cmp); sort(mac + 1,mac + 1 + n,cmp);
        LL ans = 0,sum = 0;
        memset(pos,0,sizeof(pos));
        for(int i = 1,j = 1;i <= m;i ++)
        {
            while(j <= n && mac[j].a >= tsk[i].a)
                pos[mac[j].b] ++,j ++;
            for(int x = tsk[i].b;x <= 100;x ++)
                if(pos[x])
                    { pos[x] --,ans ++,sum += tsk[i].a * 500 + tsk[i].b * 2; break; }
        }
        printf("%I64d %I64d\n",ans,sum);
    }
    return 0;
}


F : hdu3714

有1w条开口向上的二次函数,定义$F_i=max{f_i}$,求$F_i$极小值。

容易发现$F_i$也是开口向上的单峰函数,三分即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

typedef double LD;
const int SZ = 10010;

int n,a[SZ],b[SZ],c[SZ];

LD f(LD x,int i)
{
    return a[i] * x * x + b[i] * x + c[i];
}


LD get_max(LD x)
{
    LD ans = f(x,1);
    for(int i = 2;i <= n;i ++)
        ans = max(ans,f(x,i));
    return ans;
}

LD div3()
{
    LD l = 0,r = 1000;
    for(int i = 1;i <= 150;i ++)
    {
        LD m1 = l + (r - l) / 3;
        LD m2 = r - (r - l) / 3;
        LD y1 = get_max(m1),y2 = get_max(m2);
        if(y1 >= y2) l = m1;
        else r = m2;
    }
    return get_max(l);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T --)
    {
        scanf("%d",&n);
        for(int i = 1;i <= n;i ++)
            scanf("%d%d%d",&a[i],&b[i],&c[i]);
        printf("%.4lf\n",div3());
    }

    return 0;
}


G :codeforces - 752E

知道二分后思路就很简单:二分答案,然后切割到再切割就小于mid就停止。

check直接写很蛋疼,可以用一个形如dp的东西。

也有做法是用堆直接模拟,需要把重复元素合并。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

typedef long long LL;

const int SZ = 1000010;

int a[SZ],n,m,maxn,f[10000010];

LL check(int mid)
{
    memset(f,0,sizeof(f));
    for(int i = mid;i <= maxn;i ++)
        f[i] = f[i / 2] + f[(i + 1) / 2],f[i] = max(f[i],1);
    LL ans = 0;
    for(int i = 1;i <= n;i ++)
        ans += f[a[i]];
    return ans;
}

int div()
{
    int l = 1,r = maxn + 1;
    while(r - l > 1)
    {
        int mid = l + r >> 1;
        if(check(mid) >= m) l = mid;
        else r = mid;
    }
    return l;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T --)
    {
        LL sum = 0;
        maxn = 0;
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= n;i ++)
            scanf("%d",&a[i]),sum += a[i],maxn = max(maxn,a[i]);
        if(sum < m)
            puts("-1");
        else
            printf("%d\n",div());
    }

    return 0;
}


H : poj3258

NOIP2015D2T1跳石头,不说了没意思……

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 500010;
const int INF = 1000000010;

int a[SZ];
int L,n,m;

int check(int mid)
{
//    cout << mid << endl;
    int ans = 0,l = 0;
    for(int i = 1;i <= n;i ++)
    {
        if(a[i] - a[l] < mid)
            ans ++;//cout << a[i] << " " << a[l] << endl;
        else
            l = i;
    }
//    cout << ans << endl;
//    puts("--------------");
    return ans;
}

int div()
{
    int l = -1,r = L + 1;
    while(r - l > 1)
    {
        int mid = l + r >> 1;
        if(check(mid) > m) r = mid;
        else l = mid;
    }
    return l;
}

int main()
{

    scanf("%d%d%d",&L,&n,&m);
    int minn = INF;
    for(int i = 1;i <= n;i ++)
        scanf("%d",&a[i]);
    sort(a + 1,a + 1 + n);
    a[++ n] = L;
    for(int i = 1;i <= n;i ++)
        minn = min(minn,a[i] - a[i - 1]);
    if(n == 0 || n == m)
        { printf("%d\n",L); return 0; }
    if(m == 0)
        { printf("%d\n",minn); return 0; }
    //check(2);
    printf("%d\n",div());
    return 0;
}
/*
25 5 0
2
14
11
21
17

20 2 1
5 19
*/


I : poj3579

给一列数,他们两两相减的绝对值有$C_n^2$个,问这些数的中位数是多少。偶数取第$C_n^2/2$个。

二分答案,排序后计算小于等于答案的个数。验证可以二分查找$O(nlog^2n)$,也可以用指针扫过去$O(nlogn)$。

说一下lower_bound和upper_bound。

lower_bound:返回第一个大于等于x的第一个指针。

upper_bound:返回第一个大于x的第一个指针,

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

typedef long long LL;

const int SZ = 100010;
const int INF = 1000000010;

int a[SZ];
int n;
LL k;

LL check(int mid)
{
    LL ans = 0;
    for(int i = 1;i < n;i ++)
    {
        int x = upper_bound(a + i,a + 1 + n,a[i] + mid) - a - 1;
        ans += (LL)x - i;
    }
    return ans;
}

int div()
{
    int l = -1,r = INF + 1;
    while(r - l > 1)
    {
        int mid = l + r >> 1;
        if(check(mid) >= k) r = mid;
        else l = mid;
    }
    return r;
}

int main()
{
    while(~scanf("%d",&n))
    {
        for(int i = 1;i <= n;i ++)
            scanf("%d",&a[i]);
        sort(a + 1,a + 1 + n);
        k = (LL)n * (n - 1) / 2;
        k = k + 1 >> 1;
        //check(1);
        printf("%d\n",div());
    }
    return 0;
}


J : poj2976

一眼01分数规划,不说了。

注意m可能为0。

哦对,double的输出要用%f。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

typedef long long LL;
typedef double D;

const int SZ = 100010;
const int INF = 1000000010;

D a[SZ],b[SZ];
int n,m;
D tmp[SZ];

D check(D mid)
{
    D ans = 0;
    for(int i = 1;i <= n;i ++)
        tmp[i] = (D)a[i] - mid * b[i];
    sort(tmp + 1,tmp + 1 + n);
    for(int i = n;i >= n - m + 1;i --)
        ans += tmp[i];
    return ans;
}

D div()
{
    D l = 0,r = 1;
    for(int i = 1;i <= 100;i ++)
    {
        D mid = (l + r) / 2;
        if(check(mid) >= 0) l = mid;
        else r = mid;
    }
    return l * 100;
}

int main()
{
    while(scanf("%d%d",&n,&m) && n + m)
    {
        m = n - m;
        for(int i = 1;i <= n;i ++)
            scanf("%lf",&a[i]);
        for(int i = 1;i <= n;i ++)
            scanf("%lf",&b[i]);
        printf("%.0f\n",div());
    }
    return 0;
}

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

贪心二分&&三分算法模拟赛
最后由DQS修改于2017-08-06 02:43
发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆