簡單貪心

1.P10452 貨倉選址 - 洛谷

?

#include<iostream>
#include<algorithm>
using namespace std;typedef long long LL;
const int N = 1e5+10;
LL a[N];
LL n;int main()
{cin>>n;for(int i = 1;i <= n;i++)cin>>a[i];sort(a+1,a+1+n);//排序 LL sum = 0;//for(int i = 1;i <= n;i++)//{//	sum+=(abs(a[i]-a[(1+n)/2]));//}for(int i = 1;i <= n/2;i++){sum += abs(a[i]-a[n+1-i]);}cout<<sum<<endl;return 0;} 

2.P1115 最大子段和 - 洛谷

#include<iostream>using namespace std;typedef long long LL;const int N = 2e5+10;
LL a[N];
LL n;int main()
{cin>>n;for(int i = 1;i <= n;i++)cin>>a[i];LL sum = 0;LL ret = -1e5;for(int i = 1;i <= n;i++){sum+=a[i];ret = max(sum,ret);if(sum < 0)sum = 0;} cout<<ret<<endl;return 0;} 

舍棄的想法很大膽，也很有風險，但通過證明，就可以表示通過

3.?P1094 [NOIP 2007 普及組] 紀念品分組 - 洛谷

#include<iostream>
#include<algorithm>
using namespace std;int w,n;
const int N = 3e4+10;
int a[N];int main()
{cin>>w>>n;for(int i = 1;i <= n;i++)cin>>a[i];//排序sort(a+1,a+1+n);int l = 1,r = n,ret = 0;while(l <= r){//最小和最大相加小于w，符合 ，同時異位 if(a[l]+a[r]<=w)l++,r--;//l待定。r-- else{r--;}ret++;}cout<<ret<<endl;return 0;}

?4.P1056 [NOIP 2008 普及組] 排座椅 - 洛谷

#include<iostream>
#include<algorithm>
using namespace std;int m, n, k, l, d;
const int N = 1010;struct  node
{int index;//存行列的下標int cnt;//存取該行或者該列能隔開多少對同學
}row[N],col[N];//按照cnt從大到小排列
bool cmp1(node& x, node& y)
{return x.cnt > y.cnt;
}
//按照下標從小到大排列
bool cmp2(node& x, node& y)
{return x.index < y.index;
}int main()
{cin >> m >> n >> k >> l >> d;//初始化數組，賦值indexfor (int i = 1; i <= m; i++)row[i].index = i;for (int i = 1; i <= n; i++)col[i].index = i;//計算cntwhile (d--){int x, y, p, q; cin >> x >> y >> p >> q;if (x == p)col[min(y, q)].cnt++;elserow[min(x, p)].cnt++;}//通過cnt把大的排在前面-->cmp1sort(row + 1, row + 1 + m, cmp1);sort(col + 1, col + 1 + n, cmp1);//把前k或者l大的按照下表從小到大進行排列sort(row + 1, row + 1 + k, cmp2);sort(col + 1, col + 1 + l, cmp2);//輸出//行for (int i = 1; i <= k; i++){cout << row[i].index << " ";}cout << endl;//列for (int i = 1; i <= l; i++){cout << col[i].index << " ";}return 0;
}

1.把每一行和每一列可以隔開的同學記錄到cnt中

2.按照cnt從大到小進行排列

3.按照index對前k或者l個進行從小到大的排列

4.輸出前k 或 l的index下標

4.矩陣消除游戲?

?

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;int calc(int x)
{int ret = 0;while (x){x = x & (x - 1);ret++;}return ret;
}bool cmp(int x, int y)
{return x > y;
}int n, m,k;
const int N = 100;
int a[N][N];
int col[N];int main()
{cin >> n >> m >> k;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cin >> a[i][j];}}int sum = 0, ret = 0;//暴力枚舉所有的第一行for (int st = 0; st < (1 << n); st++){sum = 0;int num_1 = calc(st);//超過就不要了if (num_1 > k)continue;memset(col, 0, sizeof(col));for (int i = 0; i < n; i++){//加上當前行的數字for (int j = 0; j < m; j++){if (((st >> i) & 1) == 1){sum += a[i][j];}else{col[j] += a[i][j];}}}//對列進行從大到小排序，取前k - num_1個int remain = k - num_1;sort(col, col + m, cmp);for (int i = 0; i < remain; i++)sum += col[i];ret = max(ret, sum);}cout << ret << endl;return 0;
}

推公式

1.在確定好的順序序列中，拿出相鄰的兩個元素
2.交換這兩個元素，對前面和后面確定好順序的序列的結果不造成影響
3.根據這兩個原色交換前后的結果推導出排序的規

1.P1012 [NOIP 1998 提高組] 拼數 - 洛谷

#include<iostream>#include<algorithm>
using namespace std;int n;
const int N = 25;
string st[N];bool cmp(string& x, string& y)
{return x + y > y + x;
}int main()
{cin >> n;for (int i = 0; i < n; i++)cin >> st[i];sort(st, st+n, cmp);for (int i = 0; i < n; i++)cout << st[i];return 0;
}

?比較方法：兩兩元素相拼，

2.P2878 [USACO07JAN] Protecting the Flowers S - 洛谷

很震驚！！?

1.在確定好的順序序列中，拿出相鄰的兩個元素
2.交換這兩個元素，對前面和后面確定好順序的序列的結果不造成影響
3.根據這兩個原色交換前后的結果推導出排序的

#include<iostream>
#include<algorithm>
using namespace std;typedef long long LL;LL n;
const int N = 1e5+10;
struct node
{LL t;//時間LL d;//吃草速度 
}a[N]; bool cmp(node& x,node&y)
{return x.t*y.d < x.d*y.t;
}int main()
{cin>>n;for(int i = 1;i <= n;i++){cin>>a[i].t>>a[i].d;}sort(a+1,a+n+1,cmp);LL ret = 0,t = 0;for(int i = 1;i <= n;i++){ret += a[i].d*t;t += 2*a[i].t;}cout<<ret<<endl;} 

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

#include<iostream>
#include<algorithm>using namespace std;typedef long long LL;const int N = 5e4+10;
int n;struct node
{LL w;LL s;	
}a[N];
//推公式得到，把max中較小的放在前面，會讓總體壓力值變得較小 
bool cmp(node&x,node&y)
{return max(-x.s,x.w-y.s) < max(-y.s,y.w-x.s);
}int main()
{cin>>n;for(int i = 1;i <= n;i++){cin>>a[i].w>>a[i].s;}sort(a+1,a+1+n,cmp);LL w = 0;LL ret = -1e5;for(int i = 1;i <= n;i++){ret = max(ret,w - a[i].s);w+=a[i].w;}cout<<ret<<endl;return 0;} 

哈夫曼樹?

1.P1090 [NOIP 2004 提高組] 合并果子 - 洛谷?

#include<iostream>
#include<queue>
#include<vector>
using namespace std;typedef long long LL; priority_queue<LL,vector<LL>,greater<LL>>heap;LL n;
int main()
{cin>>n;for(int i = 1;i <= n;i++){LL x;cin>>x;heap.push(x);}LL sum = 0;while(heap.size()>1){LL x = heap.top();heap.pop();LL y = heap.top();heap.pop();sum+=(x+y);heap.push(x+y);} cout<<sum<<endl;
}

?區間問題

這種題?的解決?式?般就是按照區間的左端點或者是右端點排序，然后在排序之后的區間上，根據 題?要求，制定出相應的貪?策略，進?得到最優解。

具體是根據左端點還是右端點排序？升序還是降序？?般是假設?種排序?式，并且制定貪?策略， 當沒有明顯的反例時，就可以嘗試去寫代碼。

1.P1803 凌亂的yyy / 線段覆蓋 - 洛谷

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6+10;
int n;
struct node
{int s;int e;
}a[N];bool cmp(node&x,node&y)
{return x.s < y.s;} int main()
{cin>>n;for(int i = 1;i <= n;i++){cin>>a[i].s;cin>>a[i].e;}sort(a+1,a+1+n,cmp);//按照起點開始由小到大的順序排列int ret = 1;int r = a[1].e;for(int i = 2;i <= n;i++){int right = a[i].e,left = a[i].s;if(left < r)//重疊了，不能參加,如果重疊的右端比前面那一個還小，那就貪，覆蓋前面哪一個 {r = min(r,right);}else{ret++;//沒有重疊，可以參加r = right;//更新較小的r } }cout<<ret<<endl;return 0;} 

?

2.UVA1193 Radar Installation - 洛谷

按照左端點排序，互相重疊的區間是連續的?

二維問題轉化成一維問題?

證明：?按照左端點排序，互相重疊的區間是連續的?

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;const int N = 1e3+10;int n,d;
struct node
{double l;double r;
}a[N];bool cmp(node&x,node&y)
{return x.l < y.l;
}
int main()
{int cnt = 1;while(cin>>n>>d&&(n&&d)){int flag = 1;for(int i = 1;i <=		 n;i++){int x,y;cin>>x>>y;if(y > d)flag = -1;//把二維映射到一維上去double l =  sqrt(d*d - y*y);a[i].l = x - l;a[i].r = x + l;}sort(a+1,a+1+n,cmp);int ret = 1;int r = a[1].r; cout<<"Case "<<cnt<<": ";cnt++; for(int i = 2;i <= n;i++){int left = a[i].l,right = a[i].r;if(left<=r)//等于也可以掃到 {//掃描通過r =  min(r,right);}else{ret++;r = right;}}cout<<ret<<endl;
}return 0;} 

3.P2887 [USACO07NOV] Sunscreen G - 洛谷

?

#include<iostream>
#include<algorithm> 
using namespace std;const int N = 3e3+10;int n,l;
struct node
{int l;//表示奶牛耐受的最小值//防曬霜的防曬值 int r;//奶牛耐受的最大值// 防曬霜的數量 
}a[N],b[N]; bool cmp(node&x,node&y)
{return x.l > y.l;
}
int main()
{cin>>n>>l;for(int i = 1;i <= n;i++){cin>>a[i].l>>a[i].r;//輸入奶牛耐受值 }for(int i = 1;i <= l;i++){cin>>b[i].l>>b[i].r;//輸入防曬霜的防曬值和數量 }//按照奶牛奶牛左端從大到小進行排序sort(a+1,a+1+n,cmp);//按照防曬霜防曬值從大到小進行排序sort(b+1,b+1+l,cmp);int ret = 0;for(int i = 1;i <= n;i++){//選擇一種防曬霜for(int j = 1;j <= l;j++)	{if(b[j].r == 0)continue;if(b[j].l<=a[i].r&&b[j].l>=a[i].l){//符合條件，ret++,數量-- ret++;b[j].r--;break;//選完一個就直接除去，免得后面的都沒了 }}} cout<<ret<<endl;return 0; 
}

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

#include<iostream>
#include<queue> 
#include<algorithm>
using namespace std;
const int N = 5e4 + 10;
int n;
struct node
{int l;//牛牛的開始//該牛棚的結束時間 int r;//牛牛的結束 //該牛棚的編號 int num;//這只牛的編號 bool operator<(const node& y)const{return l > y.l;//創建小根堆 }
}a[N];
bool cmp(node& x, node& y)
{return x.l < y.l;
}
int res[N];//記錄每只牛進入的牛棚順序 
priority_queue<node> heap;//建議一個關于牛棚結束時間的小根堆，找出當前技術時間最早的，拉出來 
int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i].l >> a[i].r;a[i].num = i;}//按照左端點從小到大排列sort(a + 1, a + 1 + n, cmp);int ret = 1;//記錄牛棚狀態heap.push({ a[1].r,1 });res[a[1].num] = 1; //一號牛進一號棚 for (int i = 2; i <= n; i++){int l = a[i].l, r = a[i].r;int ete = heap.top().l;int num_peng = heap.top().r;if (ete >= l)//如果最短結束時間都>這只牛的開始的起始時間，那么就必須新開一個牛棚 {ret++;heap.push({ r,ret });res[a[i].num] = ret;}else//可以拿下 {heap.pop();//結束不要了 heap.push({ r,num_peng });//把這只牛推入彭中 res[a[i].num] = num_peng;}}cout << ret << endl;for (int i = 1; i <= n; i++)cout << res[i] << endl;
}

P2859 [USACO06FEB] Stall Reservations S - 洛谷