环保局网站建设 自查报告,wordpress导航改哪个php文件,电子商务网站类型,vr成品网站源码在线观看文章目录 贪心区间问题区间选点区间合并区间覆盖 哈夫曼树#xff08;堆#xff09;合并果子 排序不等式排队打水 绝对值不等式货仓选址 推出来的不等式耍杂技的牛 以前的题 贪心 贪心#xff1a;每一步行动总是按某种指标选取最优的操作来进行#xff0c; 该指标只看眼前堆合并果子 排序不等式排队打水 绝对值不等式货仓选址 推出来的不等式耍杂技的牛 以前的题 贪心 贪心每一步行动总是按某种指标选取最优的操作来进行 该指标只看眼前并不考虑以后可能造成的影响。 局部最优 → 整体最优。 区间问题
区间选点
给定 N 个闭区间 [ai,bi][ai,bi]请你在数轴上选择尽量少的点使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数 N表示区间数。
接下来 N 行每行包含两个整数 ai,bi表示一个区间的两个端点。
输出格式
输出一个整数表示所需的点的最小数量。
数据范围
1≤N≤105, −109≤ai≤bi≤109 此题同理最大不相交区间数量 给定 NN 个闭区间 [ai,bi][ai,bi]请你在数轴上选择若干区间使得选中的区间之间互不相交包括端点。 思路 右端点排序直接对比。下面是题解 左端点排序的话逆序对比。 #includeiostream
#includealgorithm
using namespace std;const int N 1e510;
pairint,int v[N];
bool cmp(pairint,int a,pairint,int b)
{return a.secondb.second;
}
int main(void)
{int n;scanf(%d,n);for(int i0;in;i)cinv[i].firstv[i].second;sort(v,vn,cmp);int res 0,ed -2e9;for(int i0;in;i){if(v[i].firsted) {res;ed v[i].second;}}coutres;
}区间合并
给定 N 个闭区间 [ai,bi][ai,bi]请你将这些区间分成若干组使得每组内部的区间两两之间包括端点没有交集并使得组数尽可能小。
输出最小组数。
输入格式
第一行包含整数 N表示区间数。
接下来 N 行每行包含两个整数 ai,bi表示一个区间的两个端点。
输出格式
输出一个整数表示最小组数。
数据范围
1≤N≤105, −109≤ai≤bi≤109 左端点排序 1.逻辑解释 当第cnt个区间的左端点小于前cnt - 1个区间的最小的max_r时前cnt -1个区间的左端点不一定都小于第cnt个区间的左端点因为是按照右端点排序的。如果有些区间的左端点大于第cnt个区间的左端点并且大于另一些区间的max_r就不能保证这cnt个区间都有一个共同点就是第cnt个区间的左端点。 2.反证解释 按照右边排序的话各个区间的左端点不能保证单调性所以有可能第三个区间的左端点比第一个区间的左端点还要左边它可以特别长。 反例 [1, 3], [2, 5], [4, 100], [10, 13] 3.比喻 比如有n个人需要用教室每个人占用教室的起始时间和终止时间是不一样的。 1、如果想知道只有一间教室能安排下的最多不冲突人数不是所有的人都有机会有的会被舍掉是多少区间选点和最大不相交问题那么当然是最先结束的人排在前面这样后面的人才有更多机会。如果是按左端点排序那么如过一个人0点开始用那么肯定他排在最前面但是如果他自己就占用了24小时那么只能给他一个人用了这样就达不到最大的效果。所以按左端点排序。 2、如果想知道这些人都必须安排没有人被舍弃至少需要多少个教室能安排下区间分组问题。那么肯定是按照开始时间排序开始时间越早越优先。这样每间教室都能得到最充分的利用。 偷偷说实际按左右无所谓的。这题的区间只是一个一维坐标系如果要按右端点排序那你就从右往左找 min_r 好了。只是一个方向问题。 思路 1.将所有区间按左端点从小到大排序 2.从前往后判断 if L[i] Max_r 即是否能将其放到某个现有的组中 ①如果存在将其放进去并更新当前组的 MAX_r ②如果不存在开新组然后再将其放进去 #include iostream
#include algorithm
#include queueusing namespace std;const int N 100010;int n;
struct Range
{int l, r;bool operator (const Range W)const{return l W.l;}
}range[N];int main()
{scanf(%d, n);for (int i 0; i n; i ){int l, r;scanf(%d%d, l, r);range[i] {l, r};}sort(range, range n);priority_queueint, vectorint, greaterint heap;for (int i 0; i n; i ){//小根堆里存的是每个分组的最大右端点//当前要判断的区间的左端点至少要大于其中一个分组的最大右端点才会用更新替代开新组。auto it range[i];if (heap.empty() || heap.top() it.l) heap.push(it.r); //开新组else{heap.pop(); //不开组更新当前组的MAX_r。heap.push(it.r);}}printf(%d\n, heap.size());return 0;
}
区间覆盖
给定 N 个闭区间 [ai,bi][ai,bi] 以及一个线段区间 [s,t][s,t]请你选择尽量少的区间将指定线段区间完全覆盖。
输出最少区间数如果无法完全覆盖则输出 −1。
输入格式
第一行包含两个整数 s 和 t表示给定线段区间的两个端点。
第二行包含整数 N表示给定区间数。
接下来 N 行每行包含两个整数 ai,bi表示一个区间的两个端点。
输出格式
输出一个整数表示所需最少区间数。
如果无解则输出 −1。
数据范围
1≤N≤105, −109≤ai≤bi≤109, −109≤s≤t≤109 思路 1.从左到右按左端点排序 2.从前往后依次枚举每个区间在所有能覆盖start的区间中选择右端点最大的区间 然后将start更新成右端点最大值 #include iostream
#include algorithmusing namespace std;const int N 100010;int n;
struct Range
{int l, r;bool operator (const Range W)const{return l W.l;}
}range[N];int main()
{int st, ed;scanf(%d%d, st, ed);scanf(%d, n);for (int i 0; i n; i ){int l, r;scanf(%d%d, l, r);range[i] {l, r};}sort(range, range n);int res 0;bool success false;for (int i 0; i n; i ){int j i, r -2e9;while (j n range[j].l st){r max(r, range[j].r);j ;}if (r st){res -1;break;}res ;if (r ed){success true;break;}st r;i j - 1;}if (!success) res -1;printf(%d\n, res);return 0;
} Q :最后为什么是ij-1 而不是ij ? A :比如说 j扫描到了 2 此时while() 退出了 我们下次 i 应该从 2开始但是需要注意的是我们的for()循环 i ,i还会加1次 此时 我们的 i3 直接从 3 开始循环了故需要减1。 Q 那为什么不把i去掉然后i j好理解一点 A 因为j不一定会,这样可能会死循环 哈夫曼树堆
合并果子
在一个果园里达达已经将所有的果子打了下来而且按果子的不同种类分成了不同的堆。
达达决定把所有的果子合成一堆。
每一次合并达达可以把两堆果子合并到一起消耗的体力等于两堆果子的重量之和。
可以看出所有的果子经过 n−1n−1 次合并之后就只剩下一堆了。
达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家所以达达在合并果子时要尽可能地节省体力。
假定每个果子重量都为 11并且已知果子的种类数和每种果子的数目你的任务是设计出合并的次序方案使达达耗费的体力最少并输出这个最小的体力耗费值。
例如有 33 种果子数目依次为 129129。
可以先将 1、21、2 堆合并新堆数目为 33耗费体力为 33。
接着将新堆与原先的第三堆合并又得到新的堆数目为 1212耗费体力为 1212。
所以达达总共耗费体力3121531215。
可以证明 15 为最小的体力耗费值。
输入格式
输入包括两行第一行是一个整数 n表示果子的种类数。
第二行包含 n 个整数用空格分隔第 i 个整数 ai 是第 i种果子的数目。
输出格式
输出包括一行这一行只包含一个整数也就是最小的体力耗费值。
输入数据保证这个值小于 231。
数据范围
1≤n≤10000, 1≤ai≤20000
#includeiostream
#includequeue
using namespace std ;
int res;
int main(void)
{priority_queueint,vectorint,greaterint heap;int n;cinn;while(n--) {int x ;scanf(%d,x);heap.push(x);}while(heap.size()1){int a heap.top();heap.pop();int b heap.top();heap.pop();res ab;heap.push(ab);}printf(%d,res);}排序不等式
排队打水
有 n 个人排队到 11 个水龙头处打水第 ii 个人装满水桶所需的时间是 ti请问如何安排他们的打水顺序才能使所有人的等待时间之和最小
输入格式
第一行包含整数 n。
第二行包含 n 个整数其中第 i 个整数表示第 i 个人装满水桶所花费的时间 ti。
输出格式
输出一个整数表示最小的等待时间之和。
数据范围
1≤n≤105, 1≤ti≤104
#includeiostream
#includealgorithm
using namespace std;
const int N 1e510;
long long res;
int main(void)
{int a[N],n;cinn;for(int i 0;in;i){cina[i];}sort(a,an);for(int i0;in;i){res a[i]*(n-1-i);}coutres;
}绝对值不等式
货仓选址
在一条数轴上有 N 家商店它们的坐标分别为 A1∼AN。
现在需要在数轴上建立一家货仓每天清晨从货仓到每家商店都要运送一车商品。
为了提高效率求把货仓建在何处可以使得货仓到每家商店的距离之和最小。
输入格式
第一行输入整数 N。
第二行 N 个整数 A1∼AN。
输出格式
输出一个整数表示距离之和的最小值。
数据范围
1≤N≤1000001≤N≤100000, 0≤Ai≤40000
#includeiostream
#includealgorithm
using namespace std ;
const int N 1e510;
int n;
int a[N];
int res;
int main(void)
{scanf(%d,n);for(int i0;in;i){scanf(%d,a[i]);}sort(a,an);for(int i0;in;i){res abs(a[i]-a[n/2]);}coutres;
}
推出来的不等式
耍杂技的牛
农民约翰的 N 头奶牛编号为1…N计划逃跑并加入马戏团为此它们决定练习表演杂技。
奶牛们不是非常有创意只提出了一个杂技表演
叠罗汉表演时奶牛们站在彼此的身上形成一个高高的垂直堆叠。
奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。
这 N 头奶牛中的每一头都有着自己的重量 Wi 以及自己的强壮程度 Si。
一头牛支撑不住的可能性取决于它头上所有牛的总重量不包括它自己减去它的身体强壮程度的值现在称该数值为风险值风险值越大这只牛撑不住的可能性越高。
您的任务是确定奶牛的排序使得所有奶牛的风险值中的最大值尽可能的小。
输入格式
第一行输入整数 N表示奶牛数量。
接下来 N 行每行输入两个整数表示牛的重量和强壮程度第 i 行表示第 i 头牛的重量 Wi 以及它的强壮程度 Si。
输出格式
输出一个整数表示最大风险值的最小可能值。
数据范围
1≤N≤50000, 1≤Wi≤10,000, 1≤Si≤1,000,000,000 既然是推出来的不等式下面来贴下推理过程 /交换前交换后第i头牛W1W2…W(i-1) - SiW1…Wi-1Wi1 - Si第i1头牛W1W2…Wi - S(i1)W1…Wi-1 - S(i1) 去掉重复的W1…W(i-1) , 得 /交换前交换后第i头牛- SiWi1 - Si第i1头牛Wi - S(i1)- S(i1) 题目所求答案为危险系数最大值的最小值所以找到最大值就OK。 对于上表易知 Wi -S(i1) -S(i1) , Wi1-Si -Si 故交换前取最大值 Wi -S(i1) ,交换后去最大值 Wi1-Si 。 假设交换后我们得到的是最小值这样假设得到的式子能够帮助我们求得答案则有不等式 Wi - S(i1) Wi1 - Si 即交换后变小。 移项得 Wi Si Wi1 Si1 。 此时我们发现设 Q WS 只需要按照Q对输入排序(也就是完成交换的过程)再依次比较。 取Q1 … Qi 中的最小值即可。 #include iostream
#include algorithmusing namespace std;typedef pairint, int PII;const int N 50010;int n;
PII cow[N];int main()
{scanf(%d, n);for (int i 0; i n; i ){int s, w;scanf(%d%d, w, s);cow[i] {w s, w};}sort(cow, cow n);int res -2e9, sum 0;for (int i 0; i n; i ){int s cow[i].first - cow[i].second, w cow[i].second;res max(res, sum - s);sum w;}printf(%d\n, res);return 0;
}以前的题
圣诞节来临了圣诞老人准备分发糖果现
在有多箱不同的糖果每箱糖果有自己的价值和重
量每箱糖果都可以拆分成任意散装组合带走。圣
诞老人的驯鹿雪橇最多只能装下重量W的糖果请
问圣诞老人最多能带走多大价值的糖果。
#includeiostream
#includealgorithm
#includememory.h
#includeiomanip
const double eps 1e-6;
using namespace std;
int W;
double V;
struct suger{int w;int v;bool operator(const suger s){return double(v)/w-double(s.v)/s.weps;}
}sugers[110];
void greedy(int total,int n){for(int i0;in;i){if(totalsugers[i].wW){total sugers[i].w;V sugers[i].v;}else {V sugers[i].v* double(W-total)/sugers[i].w; W WW-total;break;}}
}
int main(void)
{int n,total0;cinnW;for(int i0;in;i){cinsugers[i].vsugers[i].w;}sort(sugers,sugersn);//自己写greedy(total,n);coutfixedsetprecision(1)V;}各地放了多部电影 给定每部电影的放映时间区间区间重叠的电影不可能同时
看端点可以重合问李雷最多可以看多少部电影。
int total;
struct film{int s;int e;bool operator(const film f){return ef.e;}
}f,films[110];
int main(void)
{ int n;cinn;for(int i0;in;i){cinfilms[i].sfilms[i].e;}sort(films,filmsn);total;ffilms[0];for(int i1;in;i){if(f.efilms[i].s){total;ffilms[i];}}cout endltotal;
}
有 n头牛1n50,000)要挤奶。给定每头牛挤奶的时间区
间[A,B] (1AB1,000,000A,B为整数)。
牛需要呆畜栏里才能挤奶。一个畜栏同一时间只能容纳一头牛。
问至少需要多少个畜栏才能完成全部挤奶工作以及每头牛都
放哪个畜栏里Special judged)
去同一个畜栏的两头牛它们挤奶时间区间哪怕只在端点重合也
是不可以的。
//难点优先队列的运用 配合贪心和队列的排序
//奶牛和栅栏的顺序定义operator栅栏和奶牛都需要no来记录原顺序编号
#includeiostream //因为它们都被排序打乱了
#includealgorithm //ps循环均为从1开始
#includequeue
using namespace std;
struct cow{int s;//时间区间 start -end int e;int no; //奶牛编号防止原奶牛顺序 由于进入时间的排序而被打乱 operator(const cow c){ //排序 return sc.s;}
}cows[100];
int pos[100];
typedef struct fence{int e;//栅栏的结束时间不断在变 作为队列排序依据int no; //栅栏编号方便记录奶牛进入的栅栏同样是防止队列顺序更新而失去原顺序编号 bool operator(const fence f) const {return e f.e; }fence(int e,int n):e(e),no(n){};// 对栅栏赋值。
}fen;
int total; //栅栏数
int main(void)
{ //1.奶牛赋值排序 int n;cinn;for(int i1;in;i){cincows[i].scows[i].e;cows[i].noi;//排序前在赋值no过程记录好原位置 }sort(cows1,cowsn1); //2.栅栏赋值排序 priority_queuefen pq;for(int i1;in;i){ if(pq.empty()){//情况1.最开始无奶牛 total;pq.push(fen(cows[i].e,total));pos[cows[i].no]total;}else { //情况2. next奶牛与目前栅栏冲突 fen fpq.top();//利用排序目前结束最快 找到待命栅栏 if(f.ecows[i].s){total;pq.push(fen(cows[i].e,total)); //冲突加入新栅栏编号即total pos[cows[i].no]total;}else {//情况3. 不冲突 //不冲突total不变队列弹出原奶牛压入新奶牛 pq.pop(); pos[cows[i].no]f.no; //进入编号为top待命的栅栏 pq.push(fen(cows[i].e,f.no)); //不冲突使用原栅栏}}}//3.循环结束事件结束,输出 cout totalendl;for(int i1;in;i)coutpos[i]endl;
}
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YwPjrjKm-1684146461476)(data:image/gif;base64,R0lGODlhAQABAPABAP///wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw)]
放置雷达
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-k2PNb52e-1684146461477)(data:image/gif;base64,R0lGODlhAQABAPABAP///wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw)]
#includeiostream
#includevector
#includecmath
#includealgorithm
using namespace std;
int n,d,total;
class how{public:bool operator()(pairdouble,double p1,pairdouble,double p2){return p1.firstp2.first;}
};
bool decide(vectorpairdouble,double m,int F,int i)
{for(int kF;ki;k){if(m[i].firstm[k].secondm[i].firstm[k].first)continue;else return false;}return true;}
void dfs(const vectorpairdouble,double m)
{int FNC0;while(1){ int i;for(iFNC1;in;i){ if(decide(m,FNC,i)) continue;else{FNCi;total;break;}} if(in) {total;break;}}}
int flag1;
int main(void)
{ while(cinndn!0){total0;vectorpairdouble,double m;for(int i0;in;i){int x,y;cinxy;pairdouble,double p;p.first x-sqrt(d*d-y*y);p.secondxsqrt(d*d-y*y);m.push_back(p);}sort(m.begin(),m.end(),how());dfs(m);coutcaseflag:totalendl;flag;}
}
