洛谷题单 Part 2.5 贪心

前一阵子在准备高数月考 作息有点不太正常 所以最近的进度比较慢 虽然马上就要线代离散高数期中了 但是我也会尽量多学$C++$ 不要拖累队友

贪心算法 指的是决策时都采取当前最优解的算法。有的时候，这样做确实可以获得最优解。

这类算法都要具体问题具体分析 上题

P1208 [USACO1.3]混合牛奶 Mixing Milk

传送门
按牛奶单价排序 每次无脑选牛奶单价便宜的 就是最优解

#include
using namespace std;
#define N int(2e6+100)
inline void read(int &x){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    x=s*w;
}
struct node{
    int val,num;
}vl[N];
bool cmp(node a, node b){
    if(a.val!=b.val)return a.val<b.val;
    else return a.num>b.num;
}
int n,m;
long long ans;
int main(){
    read(m),read(n);
    for(int i=1;i<=n;i++)read(vl[i].val),read(vl[i].num);
    sort(vl+1,vl+1+n,cmp);
    for(int i=1;i<=n;i++){
        if(m<=vl[i].num){ans+=m*vl[i].val;break;}
        else ans+=vl[i].num*vl[i].val,m-=vl[i].num;
    }
    cout<<ans<<endl;
}

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

P4995 跳跳！

传送门
每次取离得最远的石头 结果就是最大 好神奇
$n\le 300$甚至懒得排序 $n^2$算法绰绰有余
上代码↓

#include
#define N 330
using namespace std;
int a[N],n,now,num;
bool vis[N];
long long ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        int mx=0,x=a[i];
        for(int j=1;j<=n;j++)if(!vis[j]){
            if(abs(a[j]-now)>mx)mx=abs(a[j]-now),x=j;
        }
        vis[x]=1;ans+=(a[x]-now)*(a[x]-now);
        now=a[x];
    }
    cout<<ans<<endl;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

P1094 [NOIP2007 普及组] 纪念品分组

传送门
先将序列排序 对于每个最大价值的 看看能不能给安排上没选的最小的 安排不上就单独一组 能安排上就他俩一组
上代码↓

#include
#define N 30030
using namespace std;
inline void read(int &x){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    x=s*w;
}
int n,a[N],w,ans;
int main(){
    read(w),read(n);
    for(int i=1;i<=n;i++)read(a[i]);
    sort(a+1,a+1+n);
    int l=1,r=n;
    while(l<=r){
        if(l==r){ans++;break;}
        if(a[l]+a[r]<=w)l++,r--;
        else r--;
        ans++;
    }
    cout<<ans<<endl;
}



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

P1199 [NOIP2010 普及组] 三国游戏

传送门
因为计算机会无脑选能跟你配合默契值最高的 所以我们只需要找到每个武将和其他武将默契值第二高最高的就行
显然计算机不会赢 直接输出$1$和最大的第二高默契值就可以了
上代码↓

#include
#define N 550
using namespace std;
inline int read(){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    return s*w;
}
int n,a[N][N],w,ans,fst,scd;
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++)
            a[i][j]=a[j][i]=read();
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]>fst)scd=fst,fst=a[i][j];
            else if(a[i][j]>scd)scd=a[i][j];
        }
        if(scd>ans)ans=scd;
        fst=scd=0;
    }
    printf("1\n%d\n",ans);
}



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

P2672 [NOIP2015 普及组] 推销员

传送门
每个住户都有个距离$dis$和疲劳值$val$，对于$k$个住户，所消耗的疲劳值为 m a x { d i s } + ∑ v a l max\{dis\}+\sum val max{dis}+∑val，因此我们按$val$进行排序。
对于第$k$个答案，优先取$k$个最大疲劳值的，这样疲劳值就是最优的，但是距离不是最优的，因为距离只算最大的一个，因此我们选择舍弃疲劳值最小的去追求更大的距离。
这么比较$O(n^2)$肯定超时，所以 要预处理疲劳值的前缀和，前$i$个住户最大的距离，后$i$个住户距离*2+疲劳值最大的
上代码↓

#include
#define reg register
#define N 100010
using namespace std;
typedef long long ll;
inline void read(ll &x){
    ll s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    x=s*w;
}
struct node{
    ll dis,val;
}a[N];
bool cmp(node a, node b){
    if(a.val!=b.val)return a.val>b.val;
    else return a.dis>b.dis;
}
ll n,f[N],b[N],sum[N];    
int main(){
    read(n);
    for(reg int i=1;i<=n;i++)read(a[i].dis);
    for(reg int i=1;i<=n;i++)read(a[i].val);
    sort(a+1,a+1+n,cmp);
    for(reg int i=1;i<=n;i++)f[i]=max(f[i-1],a[i].dis*2),sum[i]=sum[i-1]+a[i].val;
    for(reg int i=n;i;i--)b[i]=max(b[i+1],a[i].dis*2+a[i].val);
    for(reg int i=1;i<=n;i++)printf("%lld\n",max(sum[i]+f[i],sum[i-1]+b[i]));
}





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

P1080 [NOIP2012 提高组] 国王游戏

假设目前前面的大臣左手乘积为$M,$对于两个大臣，左右手数分别为$l_1,l_2,r_1,r_2,$
如果大臣$1$在前面 那么这两个大臣的贡献为 m a x { M r 1 , M l 1 r 2 } max\{\frac{M}{r_1},\frac{Ml_1}{r_2}\} max{r1​M​,r2​Ml1​​}
如果大臣$2$在前面 贡献为 m a x { M r 2 , M l 2 r 1 } max\{\frac{M}{r_2},\frac{Ml_2}{r_1}\} max{r2​M​,r1​Ml2​​}
观察到$\frac{M}{r_1}<\frac{M{l}_2}{r_1},\frac{M}{r_2}<\frac{M{l}_1}{r_2}$
因此大臣$1$在前面的条件为$\frac{M{l}_1}{r_2}<\frac{M{l}_2}{r_1},$即$l_1{r}_1<l_2{r}_2,$故按照$lr$乘积排序进行贪心即可
最后记得要用高精度，不能用高精乘高精，会超时，因此换了个板子

#include
#define N 1010
#define reg register
#define FT(A,B,C) for(int A=B;A <= C;A++)
using namespace std;
typedef long long ll;
const int maxn=100010;
inline void read(int &x){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    x=s*w;
}
struct bnum{
     int data[maxn];
    bnum() {
        memset(data, 0, sizeof(data));
        data[0] = 1;
    }
    bnum(int x) {
        memset(data, 0, sizeof(data));
        data[0] = 1;
        int i = 1;
        while (x) {
            data[i++] = x % 10;
            x /= 10;
        }
        data[0] = --i;
    }
    bnum operator *(const int &x) {
        bnum a;
        int len;
        a.data[0] = data[0];
        FT(i, 1, data[0]) a.data[i] = data[i] * x;
        for (int i = 1; i <= a.data[0] || a.data[i]; len = ++i) {
            a.data[i + 1] += a.data[i] / 10;
            a.data[i] %= 10;
        }
        a.data[len] ? a.data[0] = len : a.data[0] = --len;
        return a;
    }
    bnum operator /(const int &x) {
        bnum a;
        a.data[0]=data[0];
        int rest = 0;
        for (int i = data[0]; i >= 1; i--) {
            rest = rest * 10 + data[i];
            a.data[i] = rest / x;
            rest %= x;
        }
        while (!a.data[a.data[0]] && a.data[0]>1) a.data[0]--;
        return a;
    }
    bool operator <(const bnum &x)const{
        if(data[0]==x.data[0]){
            int i;
            for(i=data[0];data[i]==x.data[i] && i > 1;i--);
            if(i >= 1) return data[i] < x.data[i];
            else return false;
        }
        else return data[0] < x.data[0];
    }
};  
  
ostream& operator << (ostream& out, const bnum &x) {
    FT(i, 1, x.data[0]) out << x.data[x.data[0] - i + 1];
    return out;
}
struct node{
    int l,r;
}a[N];
bool cmp(node a, node b){
    return a.l*a.r<b.l*b.r;
}
int n,x,y;
bnum cal,m,now;
int main(){
    read(n),read(x),read(y);
    for(reg int i=1;i<=n;i++)read(a[i].l),read(a[i].r);
    sort(a+1,a+1+n,cmp);
    a[0].l=x,a[0].r=y;
    cal=a[0].l;
    for(reg int i=1;i<=n;i++){
        if(m<cal/a[i].r)m=cal/a[i].r;
        cal=cal*a[i].l;
    }
    cout<<m<<endl;
}



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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

先写到这 后面慢慢更