蓝书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\n%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\n",ans); 36 } View Code2 按照學分排序 每次把這個作業放到截止日期前最靠后的位置去做 線段樹 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\n",ans); 58 } View Code3 在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\n",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
總結
- 上一篇： ArcObjects中的几何对象简介(一
- 下一篇： 【剑指offer】矩形覆盖