USACO Section 1.3(贪心)

混合牛奶 Mixing Milk

题意:Marry乳业从一些奶农手中采购牛奶，并且每一位奶农为乳制品加工企业提供的价格是不同的。此外，就像每头奶牛每天只能挤出固定数量的奶，每位奶农每天能提供的牛奶数量是一定的。每天Marry乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。给出Marry乳业每天对牛奶的需求量，还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。注：每天所有奶农的总产量大于Marry乳业的需求量。

分析:反正从每位奶农手中买的牛奶数量是任意的,也就是物品可拆,所以直接贪心地把牛奶价格从小到大排序,买到n个牛奶为止.

#include<bits/stdc++.h>
using namespace std;
struct cowm{
    int p,sum;
}a[5001];
bool cmp(cowm a,cowm b){return a.p<b.p;}
int main(){
    int n,m,tot=0;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>a[i].p>>a[i].sum;
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++){
        if(a[i].sum<=n){
            n=n-a[i].sum;
            tot=tot+a[i].sum*a[i].p;
        }
        else{
            tot=tot+n*a[i].p;
            break;
        }
    }
    cout<<tot;
    return 0;
}

修理牛棚 Barn Repair

题意：在一个夜黑风高,下着暴风雨的夜晚,farmer John的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假，所以牛棚没有住满。 牛棚一个紧挨着另一个被排成一行，牛就住在里面过夜。 有些牛棚里有牛，有些没有。 所有的牛棚有相同的宽度。 自门遗失以后,farmer John必须尽快在牛棚之前竖立起新的木板。 他的新木材供应商将会供应他任何他想要的长度,但是吝啬的供应商只能提供有限数目的木板。 farmer John想将他购买的木板总长度减到最少。给出:可能买到的木板最大的数目M(1<= M<=50);牛棚的总数S(1<= S<=200); 牛棚里牛的总数C(1 <= C <=S);和牛所在的牛棚的编号stall_number(1 <= stall_number <= S),计算拦住所有有牛的牛棚所需木板的最小总长度。 输出所需木板的最小总长度作为答案。

一句话题意：给定n个值，最多把n个值分成m段，使得 每段的最值之差 的和最小.

分析：贪心策略1：区间肯定越多越好，所以一定是划分为m段（这个真的想一想就明白了，我也不好解释）贪心策略2：处理出n个值的差分数组，在最大的m-1个差那里断开.

于是先将n个值从小到大排序，然后求出差分数组，再把差分数组从大到小排序，选出前m-1个值所在的断点，就得到了m段.

题目有一个坑的地方，有可能m>=n，这种情况下答案就是n，特判一下就好了.

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
int a[205],c[205];
struct ppx{
    int val,id;
}b[205];
inline bool cmp(ppx x,ppx y){return x.val>y.val;}
int main(){
    int m=read(),sum=read(),n=read();
    if(m>=n){printf("%d\n",n);return 0;}
    for(int i=1;i<=n;++i)a[i]=read();
    sort(a+1,a+n+1);
    for(int i=1;i<=n-1;++i){
        b[i].val=a[i+1]-a[i];
        b[i].id=i;
    }
    sort(b+1,b+n,cmp);
    for(int i=1;i<=m-1;++i)c[i]=b[i].id;    
    sort(c+1,c+m);
    int ans=0,last=1;
    for(int i=1;i<=m-1;++i){
        ans+=a[c[i]]-a[last]+1;
        last=c[i]+1;
    }
    ans+=a[n]-a[last]+1;
    printf("%d\n",ans);
    return 0;
}

牛式 Prime Cryptarithm

分析:难在理解题意:其实就是一个3位数乘上一个两位数得到两个三位数,然后两个三位数相加得到一个四位数(其实就是乘法的具体过程),然后这其中出现的数字都要在我们读入的n个数中,这就是一个合法的式子.求有多少个合法的式子.我们直接枚举并判断就行了.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define ll long long
using namespace std;
int bj[20];
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
inline bool pd(int n){
    while(n){
        if(!bj[n%10])return 0;
        n/=10;
    }
    return 1;
}
inline bool check(int x,int y){
    int a=x*(y%10),b=x*(y/10),cnt=x*y;
    if(a>999||b>999||cnt>9999)return 0;
    if(pd(x)&&pd(y)&&pd(a)&&pd(b)&&pd(cnt))return 1;
    else return 0;
}
int main(){
    int n=read(),ans=0;
    for(int i=1;i<=n;++i){int a=read();bj[a]=1;}
    for(int i=100;i<1000;++i)
        for(int j=10;j<100;++j)
            if(check(i,j))++ans;
    printf("%d\n",ans);
    return 0;
}

虫洞wormhole

题意:把虫洞坐标按照y从小到大排序,然后把相邻两个y相同的虫洞连边,然后DFS穷举出n个点构成的对的所有情况,对于每一种情况判断是否有环即可.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=20;
int ans,to[N],nxt[N],visit[N];
struct ppx{int x,y;}a[N];
inline bool cmp(const ppx &x,const ppx &y){return x.y==y.y?x.x<y.x:x.y<y.y;}
inline bool pd_cycle(int x){
    while(to[x]){
        if(visit[x])return 1;
        visit[x]=1;
        x=nxt[to[x]];
    }
    return 0;
}
inline void dfs(int k,int n){
    if(k>n){
        int cnt=0;
        for(int i=1;i<=n&&cnt==0;i++){
            memset(visit,0,sizeof(visit));
            if(pd_cycle(i))cnt=1;
        }
        ans+=cnt;
        return;
    }
    else if(nxt[k])dfs(k+1,n);
    else{
        for(int i=k+1;i<=n;i++)
            if(!nxt[i]){
                nxt[i]=k;nxt[k]=i;
                dfs(k+1,n);
                nxt[i]=0;nxt[k]=0;
            }
    }
}
int main(){
    int n=read();
    for(int i=1;i<=n;++i)a[i].x=read(),a[i].y=read();
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n-1;++i)if(a[i].y==a[i+1].y)to[i]=i+1;
    dfs(1,n);printf("%d\n",ans);
    return 0;
}

滑雪课程设计Ski Course Design

题意:农民约翰的农场里有N座山峰(1<=N<=1000),每座山都有一个在0到100之间的整数的海拔高度。在冬天,因为山上有丰富的积雪,约翰经常开办滑雪训练营。不幸的是,约翰刚刚得知税法在滑雪训练营方面有新变化,明年开始实施。在仔细阅读法律后,他发现如果滑雪训练营的最高和最低的山峰海拔高度差大于17就要收税。因此,如果他改变山峰的高度（使最高与最低的山峰海拔高度差不超过17）,约翰可以避免支付税收。如果改变一座山x单位的高度成本是x^2单位,约翰最少需要付多少钱?约翰只愿意改变整数单位的高度。

分析:直接枚举0到100的所有数字i作为最低海拔(其实只要枚举0到84就可以了),然后计算要把所有海拔不合法的(即小于i或者大于i+17的)变成合法的需要花费多少,取最小值即可.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1005;
int ans,a[N];
int main(){
    int n=read(),maxn=0,minn=1e9;
    for(int i=1;i<=n;++i){
        a[i]=read();
        maxn=max(maxn,a[i]);
        minn=min(minn,a[i]);
    }
    if(maxn-minn<=17){puts("0");return 0;}
    int ans=1e9;
    for(int i=0;i<=100;++i){
        int now=0;
        for(int j=1;j<=n;++j){
            if(a[j]<i)now+=(i-a[j])*(i-a[j]);
            if(a[j]>i+17)now+=(a[j]-i-17)*(a[j]-i-17);
        }
        ans=min(ans,now);
    }
    printf("%d\n",ans);
    return 0;
}

号码锁 Combination Lock

农夫约翰的奶牛不停地从他的农场中逃出来，导致了很多损害。为了防止它们再逃出来，他买了一只很大的号码锁以防止奶牛们打开牧场的门。农夫约翰知道他的奶牛很聪明，所以他希望确保它们不会在简单地试了很多不同的号码组合之后就能轻易开锁。锁上有三个转盘，每个上面有数字1..N (1 <= N <= 100)，因为转盘是圆的，所以1和N是相邻的。有两种能开锁的号码组合，一种是农夫约翰设定的，还有一种“预设”号码组合是锁匠设定的。但是，锁有一定的容错性，所以，在每个转盘上的数字都与一个合法的号码组合中相应的数字相距两个位置以内时，锁也会打开。比如说，如果农夫约翰的号码组合是(1,2,3)，预设号码组合是(4,5,6)，在转盘被设定为(1,4,5)（因为这和农夫约翰的号码组合足够接近）或(2,4,8)（因为这和预设号码组合足够接近）。注意，(1,5,6)并不会打开锁，因为它与任一号码组合都不够接近。给出农夫约翰的号码组合和预设号码组合，请计算能够开锁的不同的号码组合的数目。号码是有序的，所以(1,2,3)与(3,2,1)不同。

分析:直接枚举所有组合然后判断是否合法即可.但要注意因为1和N是相邻的,所以不仅差的绝对值小于等于2是合法的,差的绝对值大于等于n-2也是合法的.

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
int main(){
    int n=read();
    int a=read();int b=read();int c=read();
    int d=read();int e=read();int f=read();
    int ans=0;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            for(int k=1;k<=n;++k)
                if(((abs(i-a)<=2||abs(i-a)>=n-2)&&(abs(j-b)<=2||abs(j-b)>=n-2)&&(abs(k-c)<=2||abs(k-c)>=n-2))||((abs(i-d)<=2||abs(i-d)>=n-2)&&(abs(j-e)<=2||abs(j-e)>=n-2)&&(abs(k-f)<=2||abs(k-f)>=n-2)))ans++;
    printf("%d\n",ans);
    return 0;
}

USACO Section 1.3(贪心)

原文：https://www.cnblogs.com/PPXppx/p/11262977.html