蓝书1.1 贪心

New：

n个物品要在两个机器上加工 时间分别为ai bi 必须现在第一台机器上加工 求最短加工时间

Johnson算法：

N1为a<b物品集合 N2为a>=b物品集合

N1物品按a升序排序 N2按b降序排序 N1接N2为最优顺序

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #define inf 2139062143
10 #define ll long long
11 #define MAXN 1010
12 using namespace std;
13 inline int read()
14 {
15     int x=0,f=1;char ch=getchar();
16     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
17     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 int n,res,a[MAXN],b[MAXN],id[MAXN],mn[MAXN],ans[MAXN];
21 int main()
22 {
23     n=read();
24     for(int i=1;i<=n;i++) id[i]=i,a[i]=read();
25     for(int i=1;i<=n;i++) mn[i]=min(a[i],b[i]=read());
26     for(int i=1;i<=n;i++)
27         for(int j=i+1;j<=n;j++)
28             if(mn[i]>mn[j]) {swap(mn[i],mn[j]);swap(id[i],id[j]);}
29     for(int i=1,s=0,t=n+1;i<=n;i++)
30         if(mn[i]==a[id[i]]) ans[++s]=id[i];
31         else ans[--t]=id[i];
32     for(int i=1,s=0;i<=n;i++)
33         s+=a[ans[i]],res=max(res+b[ans[i]],s+b[ans[i]]);
34     printf("%d
%d",res,ans[1]);
35     for(int i=2;i<=n;i++) printf(" %d",ans[i]);
36 }
View Code

T1 数列极差

题目大意：

n个数的集合 每次可以取出两个数a b在集合中删除 加入a*b+1

求只有最后一个数时，最后一个数的最大值与最小值之差

思路：

建立大根堆 每次取出堆顶可以得到最小值

建立小根堆 每次取出堆顶可以得到最大值

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #define inf 2139062143
10 #define ll long long
11 #define MAXN 1010101
12 using namespace std;
13 inline int read()
14 {
15     int x=0,f=1;char ch=getchar();
16     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
17     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 int n,a[MAXN],x,y;
21 priority_queue <int> q1;
22 priority_queue <int,vector<int>,greater<int> > q2;
23 int main()
24 {
25     n=read();
26     for(int i=1;i<=n;i++) {a[i]=read();q1.push(a[i]);q2.push(a[i]);}
27     for(int i=1;i<n;i++)
28     {
29         x=q1.top();q1.pop();
30         y=q1.top();q1.pop();
31         q1.push(x*y+1);
32         x=q2.top();q2.pop();
33         y=q2.top();q2.pop();
34         q2.push(x*y+1);
35     }
36     printf("%d",q2.top()-q1.top());
37 }
View Code

T2 数列分段

题目大意：

n个数的数列 分成连续若干段 每段和<=m 求最少段数

思路：

只要可以加入下一个数就加入 暴力即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #define inf 2139062143
10 #define ll long long
11 #define MAXN 1010101
12 using namespace std;
13 inline int read()
14 {
15     int x=0,f=1;char ch=getchar();
16     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
17     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 int n,m,a[MAXN],ans;
21 int main()
22 {
23     n=read(),m=read();
24     for(int i=1;i<=n;i++) a[i]=read();
25     for(int i=1,s=0;i<=n;i++)
26     {
27         if(s+a[i]>m) ans++,s=0;
28         s+=a[i];
29     }
30     printf("%d",ans+1);
31 }
View Code

T3 线段

题目大意：

n条线段 求k个不相交的线段 求最大k

思路：

右端点排序 

从第一个线段开始求最大值即为所求

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #define inf 2139062143
10 #define ll long long
11 #define MAXN 1010101
12 using namespace std;
13 inline int read()
14 {
15     int x=0,f=1;char ch=getchar();
16     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
17     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 int n,ed,ans=1;
21 struct data {int x,y;}g[MAXN];
22 bool cmp(data a,data b) {return a.y<b.y;}
23 int main()
24 {
25     n=read();
26     for(int i=1;i<=n;i++) g[i].x=read(),g[i].y=read();
27     sort(g+1,g+n+1,cmp);
28     for(int i=2,ed=g[1].y;i<=n;i++)
29         if(g[i].x>=ed) ans++,ed=g[i].y;
30     printf("%d",ans);
31 }
View Code

T4 家庭作业

题目大意：

n个作业 每个有学分和截止日期 每天只能做一项作业

每个作业必须在截止日期前完成才能获得学分 求最大学分

思路：

1 按照截止日期倒序 遇到一个作业就加入大根堆 每天做大根堆的堆顶 nlogn

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #define inf 2139062143
10 #define ll long long
11 #define MAXN 1010101
12 using namespace std;
13 inline int read()
14 {
15     int x=0,f=1;char ch=getchar();
16     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
17     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 int n,ans,mx=-inf;
21 struct data {int val,t;}g[MAXN];
22 bool cmp(data a,data b) {return a.t>b.t;}
23 int main()
24 {
25     n=read();
26     priority_queue <int> q;ans=0;
27     for(int i=1;i<=n;i++) g[i].t=read(),g[i].val=read(),mx=max(mx,g[i].val);
28     if(mx<0) {puts("0");return 0;}
29     sort(g+1,g+n+1,cmp);
30     for(int i=g[1].t,pos=1;i>=1;i--)
31     {
32         while(pos<=n&&g[pos].t>=i) q.push(g[pos++].val);
33         if(!q.empty()) {ans+=q.top();q.pop();}
34     }
35     printf("%d
",ans);
36 }
View Code

2 按照学分排序 每次把这个作业放到截止日期前最靠后的位置去做 线段树 nlogn

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #define inf 2139062143
10 #define ll long long
11 #define MAXN 1010101
12 using namespace std;
13 inline int read()
14 {
15     int x=0,f=1;char ch=getchar();
16     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
17     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 int mx[MAXN<<2];
21 void build(int k,int l,int r)
22 {    
23     mx[k]=r;if(l==r) return ;
24     int mid=(l+r)>>1;
25     build(k<<1,l,mid);build(k<<1|1,mid+1,r);
26 }
27 int query(int k,int l,int r,int a,int b)
28 {
29     if(l==a&&r==b) return mx[k];
30     int mid=(l+r)>>1;
31     if(mid>=b) return query(k<<1,l,mid,a,b);
32     else if(mid<a) return query(k<<1|1,mid+1,r,a,b);
33     else return max(query(k<<1,l,mid,a,mid),query(k<<1|1,mid+1,r,mid+1,b));
34 }
35 void mdf(int k,int l,int r,int x)
36 {
37     if(l==r) {mx[k]=-1;return ;}
38     int mid=(l+r)>>1;
39     if(mid>=x) mdf(k<<1,l,mid,x);
40     else mdf(k<<1|1,mid+1,r,x);
41     mx[k]=max(mx[k<<1],mx[k<<1|1]);
42 }
43 int n,ans,x,tim;
44 struct data {int val,t;}g[MAXN];
45 bool cmp(data a,data b) {return a.val>b.val;}
46 int main()
47 {
48     n=read();
49     if(!n) {puts("0");return 0;}
50     for(int i=1;i<=n;i++) g[i].t=read(),g[i].val=read(),tim=max(g[i].t,tim);
51     sort(g+1,g+n+1,cmp);build(1,1,tim);
52     for(int i=1;i<=n;i++)
53     {
54         if((x=query(1,1,tim,1,g[i].t))==-1) continue;
55         ans+=g[i].val;mdf(1,1,tim,x);
56     }
57     printf("%d
",ans);
58 }
View Code

3 在2的基础上进行改进 使用链表+压缩路径查找最后可以使用的位置 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #define inf 2139062143
10 #define ll long long
11 #define MAXN 1010101
12 using namespace std;
13 inline int read()
14 {
15     int x=0,f=1;char ch=getchar();
16     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
17     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 int n,ans,tim,x,f[MAXN];
21 int find(int x) {return x==f[x]?x:f[x]=find(f[x]);}
22 struct data {int val,t;}g[MAXN];
23 bool cmp(data a,data b) {return a.val>b.val;}
24 int main()
25 {
26     n=read();
27     if(!n) {puts("0");return 0;}
28     for(int i=1;i<=n;i++) g[i].t=read(),g[i].val=read(),tim=max(tim,g[i].t);
29     for(int i=1;i<=tim;i++) f[i]=i;
30     sort(g+1,g+n+1,cmp);
31     for(int i=1;i<=n;i++)
32     {
33         x=find(g[i].t);
34         if(x>0) f[x]=x-1,ans+=g[i].val;
35     }
36     printf("%d
",ans);
37 }
View Code

T5 钓鱼

题目大意：

12*H个单位时间，有n个鱼池在一条直线上，一开始在1的位置，可以选择在某些鱼池上钓鱼，但是如果持续在一个鱼池上钓鱼钓鱼速度会线性减少

初始每个时间单位钓fi条，然后下一个时间单位钓fi-di条，再下一个fi-di-di条

每个鱼池和他下一个鱼池的距离是ti个时间单位，最后你可以停到任意一个鱼池上

问最多钓多少条鱼，然后输出在个鱼池的停留时间和最多的鱼数

思路：

枚举最后停留的池塘 减去所有路程的时间

然后找到这些池塘中剩余鱼数量最多的

钓一个单位，减去d i

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #define inf 2139062143
10 #define ll long long
11 #define MAXN 1010
12 #define eps 1e-3
13 using namespace std;
14 inline int read()
15 {
16     int x=0,f=1;char ch=getchar();
17     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
18     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
19     return x*f;
20 }
21 int n,k,h,tt,mx,f[MAXN],d[MAXN],t[MAXN],a[MAXN],ans,res;
22 int main()
23 {
24     n=read(),mx=0,h=read()*12;
25     for(int i=1;i<=n;i++) f[i]=read();
26     for(int i=1;i<=n;i++) d[i]=read();
27     for(int i=1;i<=n-1;i++) t[i]=read();
28     for(int s=0,x,i=1;i<=n;i++)
29     {
30         s+=t[i-1],res=0,x=h-s;
31         for(int j=1;j<=i;j++) a[j]=f[j];
32         for(int j=1;j<=x;j++)
33         {
34             mx=a[1],tt=1;
35             for(int k=2;k<=i;k++)
36                 if(a[k]>mx) mx=a[k],tt=k;
37             a[tt]-=d[tt],res+=mx;
38             if(a[tt]<0) a[tt]=0;
39         }
40         ans=max(ans,res);
41     }
42     printf("%d",ans);
43 }
View Code

T6 糖果传递

题解链接

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/yyc-jack-0920/p/9283623.html