自己做的网站数据库,做网站是干嘛,推广链接代点,托管管理系统app视频链接 :
希望下次秒懂的是算法题_哔哩哔哩_bilibili
P1094 [NOIP2007 普及组] 纪念品分组
原题链接 :
[NOIP2007 普及组] 纪念品分组 - 洛谷 思路 :
排序 贪心 双指针首先先对输入进来的数组进行排序(由小到大)运用贪心的思想 : 前后结合,令l1,rn,若a[l]a[r]w…视频链接 :
希望下次秒懂的是算法题_哔哩哔哩_bilibili
P1094 [NOIP2007 普及组] 纪念品分组
原题链接 :
[NOIP2007 普及组] 纪念品分组 - 洛谷 思路 :
排序 贪心 双指针首先先对输入进来的数组进行排序(由小到大)运用贪心的思想 : 前后结合,令l1,rn,若a[l]a[r]w,那么a[l],a[r]可以成一组l,r--,ans,否则a[r]单独成一组,r--,ans;(这个求解过程用到双指针的思想);该贪心思路在做题的时候想可能是对的但是没有细究具体的思想请参考 : 题解 P1094 【纪念品分组】 - heidoudou 的博客 - 洛谷博客
代码 :
#includebits/stdc.h
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \nusing namespace std;
typedef long long LL;
LL gcd(LL a,LL b){ return b0 ? a : gcd(b,a%b); }
LL lcm(LL a,LL b){ return a / gcd(a,b) * b ; }
bool is_prime(int x){if(x2) return false;
for(int i2;ix/i;i) if(x%i0) return false; return true;}
const int N 3e410,mod 1e97;
int n,w,a[N];
LL ans;inline void solve(){cinwn;for(int i1;in;i) cina[i];sort(a1,a1n);int l1,rn;while(lr){if(a[l]a[r]w){l; r--; ans ;}else {r--; ans ;}}coutans endl;
}int main()
{IOSint _;// cin _;_ 1; while(_ --) solve();return 0;
} P1102 A-B 数对
原题链接 :
https://www.luogu.com.cn/problem/P1102
思路 :
1.直接暴力,当然会tle了,hh( O(n^2) )
2.妙用map;(O(n))
3.用二分函数,upper_bound和lower_bound;对于a[i](a),其后满足 b-ac的连续区间长度可以用二分函数来求得(当然是对于排好序的数组) O(nlogn)
详细解答请看代码 :
代码 :
代码(暴力) : 直接暴力,当然会收获tle(3个),hhh
#includebits/stdc.h
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \nusing namespace std;
typedef long long LL;
LL gcd(LL a,LL b){ return b0 ? a : gcd(b,a%b); }
LL lcm(LL a,LL b){ return a / gcd(a,b) * b ; }
bool is_prime(int x){if(x2) return false;
for(int i2;ix/i;i) if(x%i0) return false; return true;}
const int N 2e510,mod 1e97;
LL n,c,a[N];
LL ans;inline void solve(){cinnc;for(int i1;in;i) cina[i];for(int i1;in;i){for(int ji1;jn;j){if( (LL)(abs(a[i]-a[j])) c )ans ;}}cout ans endl;
}int main()
{IOSint _;// cin _;_ 1; while(_ --) solve();return 0;
}
代码(用map) :
// map
#includebits/stdc.h
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \nusing namespace std;
typedef long long LL;
LL gcd(LL a,LL b){ return b0 ? a : gcd(b,a%b); }
LL lcm(LL a,LL b){ return a / gcd(a,b) * b ; }
bool is_prime(int x){if(x2) return false;
for(int i2;ix/i;i) if(x%i0) return false; return true;}
const int N 2e510,mod 1e97;
LL n,c,a[N];
LL ans;
mapLL,LL mp;inline void solve(){cinnc;for(int i1;in;i) cina[i],mp[a[i]];for(int i1;in;i) ans mp[a[i]-c];cout ans endl;
}int main()
{IOSint _;// cin _;_ 1; while(_ --) solve();return 0;
}代码 : (二分) :
#includebits/stdc.h
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \nusing namespace std;
typedef long long LL;
LL gcd(LL a,LL b){ return b0 ? a : gcd(b,a%b); }
LL lcm(LL a,LL b){ return a / gcd(a,b) * b ; }
bool is_prime(int x){if(x2) return false;
for(int i2;ix/i;i) if(x%i0) return false; return true;}
const int N 2e510,mod 1e97;
LL n,c,a[N];
LL ans;inline void solve(){cinnc;for(int i1;in;i) cina[i];sort(a1,an1);for(int i1;in;i){ans ((upper_bound(a1,an1,a[i]c)-a)-(lower_bound(a1,an1,a[i]c)-a));}cout ans endl;
}int main()
{IOSint _;// cin _;_ 1; while(_ --) solve();return 0;
}
P1105 平台
原题链接 :
平台 - 洛谷
思路 :
结构体排序 暴力,其实不难要注意细节
不然就像这样(aaa) : 第一次排序规则 : 高度优先编号其次由小到大
第二次排序规则 : 编号优先,由小到大;
注意 :
边界相同落到下一个上面注意结构体排序的规则!!!
代码 :
#includebits/stdc.h
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \nusing namespace std;
typedef long long LL;
LL gcd(LL a,LL b){ return b0 ? a : gcd(b,a%b); }
LL lcm(LL a,LL b){ return a / gcd(a,b) * b ; }
bool is_prime(int x){if(x2) return false;
for(int i2;ix/i;i) if(x%i0) return false; return true;}
const int N 1e410;
int n,xl,xr;
struct Node{int idx,h,l,r,yl,yr;bool operator (const Node u) const{return h u.h ? idx u.idx : h u.h;}
}a[N];bool cmp(const Node x,const Node y){return x.idx y.idx;
}inline void solve(){cinn;for(int i1;in;i){cina[i].ha[i].la[i].r;a[i].idx i;}sort(a1,an1);for(int i1;in;i){xl0,xr0;for(int ji-1;j1;j--){if(a[j].la[i].l a[j].ra[i].l a[j].h a[i].h){xl a[j].idx;break;}}for(int ji-1;j1;--j){if(a[j].ra[i].r a[j].la[i].r a[j].h a[i].h){xr a[j].idx;break;}}a[i].yl xl;a[i].yr xr;}sort(a1,an1,cmp);for(int i1;in;i){cout a[i].yl a[i].yr endl;}
}int main()
{IOSint _;// cin _;_ 1; while(_ --) solve();return 0;
}EK的代码中是用的一个pairint,int来存yl,yr信息思想是一样!!!
P1111 修复公路
原题链接 :
修复公路 - 洛谷
思路 :
并查集
代码(cv!):
#includebits/stdc.h
using namespace std;
int fa[100010],n,m;
struct node
{int x,y,t;
}a[10000010];//结构体大法好
bool cmp(node fir,node sec)
{return fir.tsec.t;
}//按照时间排序
int gf(int x)
{if(fa[x]x) return x;return fa[x]gf(fa[x]);//这句是路径压缩前面的题解已经说过此处不再阐述
}
void hb(int x,int y)
{int fxgf(x);//找到x的祖先int fygf(y);//找到y的祖先fa[fx]fy;//让fx认fy为祖先
}//合并操作
bool check()
{int sum0;for(int i1;in;i){if(fa[i]i) sum;//统计独立集合的个数if(sum2) return 0;//发现有两个就返回false应该会省一点时间}return 1;//只有1个集合返回true
}//判断集合个数
int main()
{scanf(%d%d,n,m);for(int i1;in;i) fa[i]i;//初始化for(int i1;im;i) scanf(%d%d%d,a[i].x,a[i].y,a[i].t);sort(a1,am1,cmp);//按时间排序for(int i1;im;i){hb(a[i].x,a[i].y);//进行合并if(check())//如果只有1个集合{printf(%d\n,a[i].t);//输出时间return 0;//愉快的结束主程序}}printf(-1\n);//所有公路修完了仍没有联通集合个数2输出-1return 0;//愉快的结束主程序
}
P1115 最大子段和
原题链接 :
最大子段和 - 洛谷
思路 :
贪心由前向后遍历sum记录和如果sum0的话sum0(不然的话只会对后面的sum产生负影响),循环更新ans max(ans,sum);
代码 :
#includebits/stdc.h
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \nusing namespace std;
typedef long long LL;
int gcd(int a,int b){ return b0 ? a : gcd(b,a%b); }
int lcm(int a,int b){ if(a0||b0) return 0; return (a*b)/gcd(a,b); }
bool is_prime(int x){if(x2) return false;
for(int i2;ix/i;i) if(x%i0) return false; return true;}
const int N 2e510;
int n,x;
LL sum0,ans -1e9;inline void solve(){cinn;for(int i1;in;i){cinx;sum x;ans max(ans,sum);if(sum 0) sum 0;}cout ans endl;
}int main()
{IOSint _;// cin _;_ 1; while(_ --) solve();return 0;
}
