目錄

• 1055. 股票買賣 II
• 104. 貨倉選址
• 112. 雷達設備 【有意思的區(qū)間合并】

1055. 股票買賣 II

https://www.acwing.com/problem/content/1057/

思路: 只要相鄰的兩個數(shù)，后面的比前面的大 就交易。

#include<cstdio> #include<iostream>using namespace std;const int N=10010;int p[N]; int n; int ans; int main(void) {cin>>n;for(int i=0;i<n;i++) cin>>p[i];for(int i=0;i+1<n;i++){if(p[i]<p[i+1]){ans+=p[i+1]-p[i];}}cout<<ans<<endl;return 0; }

104. 貨倉選址

https://www.acwing.com/problem/content/106/

當只有兩個商店的時候，你會發(fā)現(xiàn)倉庫一定要建在A和B之間(包括A和B的位置)。


當上商店有三個的時候，倉庫一定在中間的商店的位置。


當商店有4個的時候，倉庫要放在中間的兩個商店中間的任意位置。

綜上所述，最佳的位置就是中位數(shù)，特別要注意的是，是中位數(shù)，即商店位置中間的那個數(shù)。
當是偶數(shù)的話，中間的倆都可以。 不是最小的加最大的數(shù)除以2 的那個數(shù)。

#include<cstdio> #include<iostream> #include<algorithm> using namespace std;const int N=100100;int area[N]; int n; int ans;int main(void) {cin>>n;for(int i=0;i<n;i++) cin>>area[i];sort(area,area+n);//排好序ans=area[n/2];int sum=0;for(int i=0;i<n;i++){sum+=abs(area[i]-ans);}cout<<sum<<endl;return 0; }

112. 雷達設備 【有意思的區(qū)間合并】

#include<bits/stdc++.h> using namespace std; typedef pair<double,double> PII; int n,ans; double d,x,y; bool flag; vector<PII>ve; int main(void) {cin>>n>>d;while(n--){cin>>x>>y;if(y>d) flag=true;double l=x-sqrt(d*d-y*y);double r=x+sqrt(d*d-y*y);ve.push_back({r,l});}sort(ve.begin(),ve.end());double index=-1e9-10;for(int i=0;i<ve.size();i++) if(ve[i].second>index) ans++,index=ve[i].first;if(flag) cout<<-1;else cout<<ans;return 0; }

總結

以上是生活随笔為你收集整理的第七章：贪心习题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。