8.贪心算法

简单贪心

1.P10452 货仓选址 - 洛谷

 

1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
5. typedef long long LL;
6. const int N = 1e5+10;
7. LL a[N];
8. LL n;
10. int main()
11. {
12.         cin>>n;
13.         for(int i = 1;i <= n;i++)cin>>a[i];
14.         sort(a+1,a+1+n);//排序
15.         LL sum = 0;
16.         //for(int i = 1;i <= n;i++)
17.         //{
18.         //        sum+=(abs(a[i]-a[(1+n)/2]));
19.         //}
20.        
21.         for(int i = 1;i <= n/2;i++)
22.         {
23.                 sum += abs(a[i]-a[n+1-i]);
24.         }
25.         cout<<sum<<endl;
26.         return 0;
27. }

复制代码

2.P1115 最大子段和 - 洛谷

1. #include<iostream>
3. using namespace std;
5. typedef long long LL;
7. const int N = 2e5+10;
8. LL a[N];
9. LL n;
11. int main()
12. {
13.         cin>>n;
14.         for(int i = 1;i <= n;i++)cin>>a[i];
15.        
16.         LL sum = 0;LL ret = -1e5;
17.         for(int i = 1;i <= n;i++)
18.         {
19.                 sum+=a[i];
20.                 ret = max(sum,ret);
21.                 if(sum < 0)sum = 0;
22.          }
23.          cout<<ret<<endl;
24.          return 0;
25. }

复制代码

  舍弃的想法很大胆，也很有风险，但通过证实，就可以表现通过
  3. P1094 [NOIP 2007 遍及组] 怀念品分组 - 洛谷

1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
5. int w,n;
6. const int N = 3e4+10;
7. int a[N];
9. int main()
10. {
11.         cin>>w>>n;
12.         for(int i = 1;i <= n;i++)cin>>a[i];
13.         //排序
14.          sort(a+1,a+1+n);
15.          int l = 1,r = n,ret = 0;
16.          while(l <= r)
17.          {
18.                  //最小和最大相加小于w，符合 ，同时异位
19.                  if(a[l]+a[r]<=w)l++,r--;
20.                  //l待定。r--
21.                  else
22.                  {
23.                          r--;
24.                  }
25.                  ret++;
26.          }
27.          cout<<ret<<endl;
28.          return 0;
29.        
30. }

复制代码

 4.P1056 [NOIP 2008 遍及组] 排座椅 - 洛谷

1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
5. int m, n, k, l, d;
6. const int N = 1010;
8. struct  node
9. {
10.         int index;//存行列的下标
11.         int cnt;//存取该行或者该列能隔开多少对同学
12. }row[N],col[N];
14. //按照cnt从大到小排列
15. bool cmp1(node& x, node& y)
16. {
17.         return x.cnt > y.cnt;
18. }
19. //按照下标从小到大排列
20. bool cmp2(node& x, node& y)
21. {
22.         return x.index < y.index;
23. }
25. int main()
26. {
27.         cin >> m >> n >> k >> l >> d;
28.         //初始化数组，赋值index
29.         for (int i = 1; i <= m; i++)row[i].index = i;
30.         for (int i = 1; i <= n; i++)col[i].index = i;
31.         //计算cnt
32.         while (d--)
33.         {
34.                 int x, y, p, q; cin >> x >> y >> p >> q;
35.                 if (x == p)col[min(y, q)].cnt++;
36.                 else
37.                         row[min(x, p)].cnt++;
38.         }
39.         //通过cnt把大的排在前面-->cmp1
40.         sort(row + 1, row + 1 + m, cmp1);
41.         sort(col + 1, col + 1 + n, cmp1);
42.         //把前k或者l大的按照下表从小到大进行排列
43.         sort(row + 1, row + 1 + k, cmp2);
44.         sort(col + 1, col + 1 + l, cmp2);
45.         //输出
46.         //行
47.         for (int i = 1; i <= k; i++)
48.         {
49.                 cout << row[i].index << " ";
50.         }
51.         cout << endl;
52.         //列
53.         for (int i = 1; i <= l; i++)
54.         {
55.                 cout << col[i].index << " ";
56.         }
57.         return 0;
58. }

复制代码

  1.把每一行和每一列可以隔开的同砚纪录到cnt中
  2.按照cnt从大到小举行分列
  3.按照index对前k大概l个举行从小到大的分列
  4.输出前k 或 l的index下标
  4.矩阵消除游戏 

 

1. #include<iostream>
2. #include<algorithm>
3. #include<cstring>
4. using namespace std;
6. int calc(int x)
7. {
8.         int ret = 0;
9.         while (x)
10.         {
11.                 x = x & (x - 1);
12.                 ret++;
13.         }
14.         return ret;
15. }
17. bool cmp(int x, int y)
18. {
19.         return x > y;
20. }
22. int n, m,k;
23. const int N = 100;
24. int a[N][N];
25. int col[N];
27. int main()
28. {
29.         cin >> n >> m >> k;
30.         for (int i = 0; i < n; i++)
31.         {
32.                 for (int j = 0; j < m; j++)
33.                 {
34.                         cin >> a[i][j];
35.                 }
36.         }
37.         int sum = 0, ret = 0;
38.         //暴力枚举所有的第一行
39.         for (int st = 0; st < (1 << n); st++)
40.         {
41.                 sum = 0;
42.                 int num_1 = calc(st);
43.                 //超过就不要了
44.                 if (num_1 > k)continue;
46.                 memset(col, 0, sizeof(col));
47.                 for (int i = 0; i < n; i++)
48.                 {
49.                         //加上当前行的数字
50.                         for (int j = 0; j < m; j++)
51.                         {
52.                                 if (((st >> i) & 1) == 1)
53.                                 {
54.                                         sum += a[i][j];
55.                                 }
56.                                 else
57.                                 {
58.                                         col[j] += a[i][j];
59.                                 }
60.                         }
61.                 }
62.                 //对列进行从大到小排序，取前k - num_1个
63.                 int remain = k - num_1;
64.                 sort(col, col + m, cmp);
65.                 for (int i = 0; i < remain; i++)sum += col[i];
66.                 ret = max(ret, sum);
67.         }
68.         cout << ret << endl;
69.         return 0;
70. }

复制代码

  暴力摆列行的全部选择方法，然后设置col，纪录行选择后，列的数据，remain表现剩余的操纵次数，对摆列行排序，取最大的前remain个即可。， 
  推公式

   1.在确定好的序次序列中，拿出相邻的两个元素
2.互换这两个元素，对前面和反面确定好序次的序列的结果不造成影响
3.根据这两个原色互换前后的结果推导出排序的规
  

1.P1012 [NOIP 1998 进步组] 拼数 - 洛谷

1. #include<iostream>
3. #include<algorithm>
4. using namespace std;
6. int n;
7. const int N = 25;
8. string st[N];
10. bool cmp(string& x, string& y)
11. {
12.         return x + y > y + x;
13. }
15. int main()
16. {
17.         cin >> n;
18.         for (int i = 0; i < n; i++)
19.                 cin >> st[i];
21.         sort(st, st+n, cmp);
22.         for (int i = 0; i < n; i++)
23.                 cout << st[i];
24.         return 0;
25. }

复制代码

   比力方法：两两元素相拼，
  2.P2878 [USACO07JAN] Protecting the Flowers S - 洛谷

   很震惊！！ 
     1.在确定好的序次序列中，拿出相邻的两个元素
2.互换这两个元素，对前面和反面确定好序次的序列的结果不造成影响
3.根据这两个原色互换前后的结果推导出排序的
   

1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
5. typedef long long LL;
7. LL n;
8. const int N = 1e5+10;
9. struct node
10. {
11.         LL t;//时间
12.         LL d;//吃草速度
13. }a[N];
15. bool cmp(node& x,node&y)
16. {
17.         return x.t*y.d < x.d*y.t;
18. }
20. int main()
21. {
22.         cin>>n;
23.         for(int i = 1;i <= n;i++)
24.         {
25.                 cin>>a[i].t>>a[i].d;
26.         }
27.         sort(a+1,a+n+1,cmp);
28.         LL ret = 0,t = 0;
29.         for(int i = 1;i <= n;i++)
30.         {
31.                 ret += a[i].d*t;
32.                 t += 2*a[i].t;
33.         }
34.         cout<<ret<<endl;
35. }

复制代码

3. P1842 [USACO05NOV] 奶牛玩杂技 - 洛谷

1. #include<iostream>
2. #include<algorithm>
4. using namespace std;
6. typedef long long LL;
8. const int N = 5e4+10;
9. int n;
11. struct node
12. {
13.         LL w;
14.         LL s;       
15. }a[N];
16. //推公式得到，把max中较小的放在前面，会让总体压力值变得较小
17. bool cmp(node&x,node&y)
18. {
19.         return max(-x.s,x.w-y.s) < max(-y.s,y.w-x.s);
20. }
22. int main()
23. {
24.         cin>>n;
25.         for(int i = 1;i <= n;i++)
26.         {
27.                 cin>>a[i].w>>a[i].s;
28.         }
29.         sort(a+1,a+1+n,cmp);
30.        
31.         LL w = 0;
32.         LL ret = -1e5;
33.         for(int i = 1;i <= n;i++)
34.         {
35.                 ret = max(ret,w - a[i].s);
36.                 w+=a[i].w;
37.         }
38.         cout<<ret<<endl;
39.         return 0;
40.        
41. }

复制代码

  

  哈夫曼树 

1.P1090 [NOIP 2004 进步组] 归并果子 - 洛谷 

1. #include<iostream>
2. #include<queue>
3. #include<vector>
4. using namespace std;
6. typedef long long LL;
8. priority_queue<LL,vector<LL>,greater<LL>>heap;
10. LL n;
11. int main()
12. {
13.         cin>>n;
14.         for(int i = 1;i <= n;i++)
15.         {
16.                 LL x;cin>>x;
17.                 heap.push(x);
18.         }
19.         LL sum = 0;
20.         while(heap.size()>1)
21.         {
22.                 LL x = heap.top();heap.pop();
23.                 LL y = heap.top();heap.pop();
24.                 sum+=(x+y);
25.                 heap.push(x+y);
26.          }
27.          cout<<sum<<endl;
28. }

复制代码

 区间标题

   这种题⽬的办理⽅式⼀般就是按照区间的左端点大概是右端点排序，然后在排序之后的区间上，根据 题⽬要求，订定出相应的贪⼼计谋，进⽽得到最优解。
  
  具体是根据左端点还是右端点排序？升序还是降序？⼀般是假设⼀种排序⽅式，而且订定贪⼼计谋， 当没有显着的反例时，就可以实验去写代码。
  1.P1803 缭乱的yyy / 线段覆盖 - 洛谷

1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
4. const int N = 1e6+10;
5. int n;
6. struct node
7. {
8.         int s;
9.         int e;
10. }a[N];
12. bool cmp(node&x,node&y)
13. {
14.         return x.s < y.s;
15. }
17. int main()
18. {
19.         cin>>n;
20.         for(int i = 1;i <= n;i++)
21.         {
22.                 cin>>a[i].s;
23.                 cin>>a[i].e;
24.         }
25.        
26.         sort(a+1,a+1+n,cmp);//按照起点开始由小到大的顺序排列
27.         int ret = 1;
28.         int r = a[1].e;
29.         for(int i = 2;i <= n;i++)
30.         {
31.                 int right = a[i].e,left = a[i].s;
32.                 if(left < r)//重叠了，不能参加,如果重叠的右端比前面那一个还小，那就贪，覆盖前面哪一个
33.                 {
34.                         r = min(r,right);
35.                 }
36.                 else
37.                 {
38.                         ret++;//没有重叠，可以参加
39.                         r = right;//更新较小的r
40.                  }
41.         }
42.         cout<<ret<<endl;
43.         return 0;
44.          
45. }

复制代码

 

2.UVA1193 Radar Installation - 洛谷

   按照左端点排序，相互重叠的区间是连续的 
    二维标题转化成一维标题 
    证实： 按照左端点排序，相互重叠的区间是连续的 
  

1. #include<iostream>
2. #include<cmath>
3. #include<algorithm>
4. using namespace std;
6. const int N = 1e3+10;
8. int n,d;
9. struct node
10. {
11.         double l;
12.         double r;
13. }a[N];
15. bool cmp(node&x,node&y)
16. {
17.         return x.l < y.l;
18. }
19. int main()
20. {
21.         int cnt = 1;
22.         while(cin>>n>>d&&(n&&d))
23.         {
24.                 int flag = 1;
25.                 for(int i = 1;i <= n;i++)
26.                 {
27.                         int x,y;cin>>x>>y;
28.                         if(y > d)flag = -1;
29.                         //把二维映射到一维上去
30.                         double l =  sqrt(d*d - y*y);
31.                         a[i].l = x - l;
32.                         a[i].r = x + l;
33.                 }
34.                 sort(a+1,a+1+n,cmp);
35.         int ret = 1;
36.         int r = a[1].r;
37.         cout<<"Case "<<cnt<<": ";
38.         cnt++;
39.         for(int i = 2;i <= n;i++)
40.         {
41.                 int left = a[i].l,right = a[i].r;
42.                 if(left<=r)//等于也可以扫到
43.                 {
44.                         //扫描通过
45.                         r =  min(r,right);
46.                 }else
47.                 {
48.                         ret++;
49.                         r = right;
50.                 }
51.         }
52.        
53.         cout<<ret<<endl;
54. }
55.         return 0;
56. }

复制代码

3.P2887 [USACO07NOV] Sunscreen G - 洛谷

 

1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
5. const int N = 3e3+10;
7. int n,l;
8. struct node
9. {
10.         int l;//表示奶牛耐受的最小值//防晒霜的防晒值
11.         int r;//奶牛耐受的最大值// 防晒霜的数量
12. }a[N],b[N];
14. bool cmp(node&x,node&y)
15. {
16.         return x.l > y.l;
17. }
18. int main()
19. {
20.         cin>>n>>l;
21.         for(int i = 1;i <= n;i++)
22.         {
23.                 cin>>a[i].l>>a[i].r;//输入奶牛耐受值
24.         }
25.         for(int i = 1;i <= l;i++)
26.         {
27.                 cin>>b[i].l>>b[i].r;//输入防晒霜的防晒值和数量
28.         }
29.         //按照奶牛奶牛左端从大到小进行排序
30.         sort(a+1,a+1+n,cmp);
31.         //按照防晒霜防晒值从大到小进行排序
32.         sort(b+1,b+1+l,cmp);
33.         int ret = 0;
34.         for(int i = 1;i <= n;i++)
35.         {
36.                 //选择一种防晒霜
37.                 for(int j = 1;j <= l;j++)       
38.                 {
39.                         if(b[j].r == 0)continue;
40.                         if(b[j].l<=a[i].r&&b[j].l>=a[i].l)
41.                         {
42.                                 //符合条件，ret++,数量--
43.                                 ret++;
44.                                 b[j].r--;
45.                                 break;//选完一个就直接除去，免得后面的都没了
46.                         }
47.                 }
48.         }
49.         cout<<ret<<endl;
50.         return 0;
51. }

复制代码

 4.P2859 [USACO06FEB] Stall Reservations S - 洛谷

1. #include<iostream>
2. #include<queue>
3. #include<algorithm>
4. using namespace std;
5. const int N = 5e4 + 10;
6. int n;
7. struct node
8. {
9.         int l;//牛牛的开始//该牛棚的结束时间
10.         int r;//牛牛的结束 //该牛棚的编号
11.         int num;//这只牛的编号
13.         bool operator<(const node& y)const
14.         {
15.                 return l > y.l;//创建小根堆
16.         }
17. }a[N];
18. bool cmp(node& x, node& y)
19. {
20.         return x.l < y.l;
21. }
22. int res[N];//记录每只牛进入的牛棚顺序
23. priority_queue<node> heap;//建议一个关于牛棚结束时间的小根堆，找出当前技术时间最早的，拉出来
24. int main()
25. {
26.         cin >> n;
27.         for (int i = 1; i <= n; i++)
28.         {
29.                 cin >> a[i].l >> a[i].r;
30.                 a[i].num = i;
31.         }
32.         //按照左端点从小到大排列
33.         sort(a + 1, a + 1 + n, cmp);
34.         int ret = 1;//记录牛棚状态
35.         heap.push({ a[1].r,1 });
36.         res[a[1].num] = 1; //一号牛进一号棚
37.         for (int i = 2; i <= n; i++)
38.         {
39.                 int l = a[i].l, r = a[i].r;
40.                 int ete = heap.top().l;
41.                 int num_peng = heap.top().r;
42.                 if (ete >= l)//如果最短结束时间都>这只牛的开始的起始时间，那么就必须新开一个牛棚
43.                 {
44.                         ret++;
45.                         heap.push({ r,ret });
46.                         res[a[i].num] = ret;
47.                 }
48.                 else//可以拿下
49.                 {
50.                         heap.pop();//结束不要了
51.                         heap.push({ r,num_peng });//把这只牛推入彭中
52.                         res[a[i].num] = num_peng;
53.                 }
54.         }
55.         cout << ret << endl;
56.         for (int i = 1; i <= n; i++)cout << res[i] << endl;
57. }

复制代码