目录
P1094 [NOIP2007 普及组] 纪念品分组
原题链接 :
思路 :
代码 :
P1102 A-B 数对
原题链接 :
思路 :
代码 :
代码(暴力) :
代码(用map) :
代码 : (二分) :
P1105 平台
原题链接 :
思路 :
代码 :
P1111 修复公路
原题链接 :
思路 :
P1115 最大子段和
原题链接 :
思路 :
代码 :
视频链接 :
秒懂算法2
P1094 [NOIP2007 普及组] 纪念品分组
原题链接 :
[NOIP2007 普及组] 纪念品分组 - 洛谷
思路 :
- 排序 + 贪心 + 双指针
- 首先先对输入进来的数组进行排序(由小到大)
- 运用贪心的思想 : 前后结合,令l=1,r=n,若a[l]+a[r]<=w,那么a[l],a[r]可以成一组,l++,r--,ans++,否则a[r]单独成一组,r--,ans++;(这个求解过程用到双指针的思想);
- 该贪心思路在做题的时候想可能是对的,但是没有细究,具体的思想请参考 : 题解 P1094 【纪念品分组】 - heidoudou 的博客 - 洛谷博客
代码 :
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){ return b==0 ? a : gcd(b,a%b); }
LL lcm(LL a,LL b){ return a / gcd(a,b) * b ; }
bool is_prime(int x){if(x<2) return false;
for(int i=2;i<=x/i;i++) if(x%i==0) return false; return true;}
const int N = 3e4+10,mod = 1e9+7;
int n,w,a[N];
LL ans;
inline void solve(){
cin>>w>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
int l=1,r=n;
while(l<=r){
if(a[l]+a[r]<=w){
l++; r--; ans ++;
}else {
r--; ans ++;
}
}
cout<<ans <<endl;
}
int main()
{
IOS
int _;
// 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-a=c的连续区间长度可以用二分函数来求得(当然是对于排好序的数组) O(nlogn)
详细解答请看代码 :
代码 :
代码(暴力) :
直接暴力,当然会收获tle(3个),hhh
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){ return b==0 ? a : gcd(b,a%b); }
LL lcm(LL a,LL b){ return a / gcd(a,b) * b ; }
bool is_prime(int x){if(x<2) return false;
for(int i=2;i<=x/i;i++) if(x%i==0) return false; return true;}
const int N = 2e5+10,mod = 1e9+7;
LL n,c,a[N];
LL ans;
inline void solve(){
cin>>n>>c;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if( (LL)(abs(a[i]-a[j])) == c )
ans ++;
}
}
cout << ans << endl;
}
int main()
{
IOS
int _;
// cin >> _;
_ = 1;
while(_ --) solve();
return 0;
}
代码(用map) :
// map
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){ return b==0 ? a : gcd(b,a%b); }
LL lcm(LL a,LL b){ return a / gcd(a,b) * b ; }
bool is_prime(int x){if(x<2) return false;
for(int i=2;i<=x/i;i++) if(x%i==0) return false; return true;}
const int N = 2e5+10,mod = 1e9+7;
LL n,c,a[N];
LL ans;
map<LL,LL> mp;
inline void solve(){
cin>>n>>c;
for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++;
for(int i=1;i<=n;i++) ans += mp[a[i]-c];
cout << ans << endl;
}
int main()
{
IOS
int _;
// cin >> _;
_ = 1;
while(_ --) solve();
return 0;
}
代码 : (二分) :
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){ return b==0 ? a : gcd(b,a%b); }
LL lcm(LL a,LL b){ return a / gcd(a,b) * b ; }
bool is_prime(int x){if(x<2) return false;
for(int i=2;i<=x/i;i++) if(x%i==0) return false; return true;}
const int N = 2e5+10,mod = 1e9+7;
LL n,c,a[N];
LL ans;
inline void solve(){
cin>>n>>c;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
ans += ((upper_bound(a+1,a+n+1,a[i]+c)-a)-(lower_bound(a+1,a+n+1,a[i]+c)-a));
}
cout << ans << endl;
}
int main()
{
IOS
int _;
// cin >> _;
_ = 1;
while(_ --) solve();
return 0;
}
P1105 平台
原题链接 :
平台 - 洛谷
思路 :
结构体排序 + 暴力,其实不难,要注意细节;
不然,就像这样(aaa) :
第一次排序规则 : 高度优先,编号其次,由小到大;
第二次排序规则 : 编号优先,由小到大;
注意 :
- 边界相同,落到下一个上面,注意结构体排序的规则!!!
代码 :
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){ return b==0 ? a : gcd(b,a%b); }
LL lcm(LL a,LL b){ return a / gcd(a,b) * b ; }
bool is_prime(int x){if(x<2) return false;
for(int i=2;i<=x/i;i++) if(x%i==0) return false; return true;}
const int N = 1e4+10;
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(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].h>>a[i].l>>a[i].r;
a[i].idx = i;
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
xl=0,xr=0;
for(int j=i-1;j>=1;j--){
if(a[j].l<a[i].l && a[j].r>a[i].l && a[j].h < a[i].h){
xl = a[j].idx;
break;
}
}
for(int j=i-1;j>=1;--j){
if(a[j].r>a[i].r && a[j].l<a[i].r && a[j].h < a[i].h){
xr = a[j].idx;
break;
}
}
a[i].yl = xl;
a[i].yr = xr;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
cout << a[i].yl << " " << a[i].yr << endl;
}
}
int main()
{
IOS
int _;
// cin >> _;
_ = 1;
while(_ --) solve();
return 0;
}
EK的代码中是用的一个pair<int,int>来存yl,yr信息,思想是一样!!!
P1111 修复公路
原题链接 :
修复公路 - 洛谷
思路 :
并查集
代码(cv!):
#include<bits/stdc++.h>
using namespace std;
int fa[1000+10],n,m;
struct node
{
int x,y,t;
}a[100000+10];//结构体大法好!
bool cmp(node fir,node sec)
{
return fir.t<sec.t;
}//按照时间排序
int gf(int x)
{
if(fa[x]==x) return x;
return fa[x]=gf(fa[x]);
//这句是路径压缩,前面的题解已经说过,此处不再阐述
}
void hb(int x,int y)
{
int fx=gf(x);//找到x的祖先
int fy=gf(y);//找到y的祖先
fa[fx]=fy;//让fx认fy为祖先
}//合并操作
bool check()
{
int sum=0;
for(int i=1;i<=n;i++)
{
if(fa[i]==i) sum++;//统计独立集合的个数
if(sum==2) return 0;//发现有两个就返回false应该会省一点时间
}
return 1;//只有1个集合,返回true
}//判断集合个数
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) fa[i]=i;//初始化
for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].t);
sort(a+1,a+m+1,cmp);//按时间排序
for(int i=1;i<=m;i++)
{
hb(a[i].x,a[i].y);//进行合并
if(check())//如果只有1个集合
{
printf("%d\n",a[i].t);//输出时间
return 0;//愉快的结束主程序
}
}
printf("-1\n");//所有公路修完了仍没有联通(集合个数>=2),输出-1
return 0;//愉快的结束主程序
}
P1115 最大子段和
原题链接 :
最大子段和 - 洛谷文章来源:https://www.toymoban.com/news/detail-681465.html
思路 :
贪心,由前向后遍历,sum记录和,如果sum<0的话,sum=0(不然的话,只会对后面的sum产生负影响),循环更新ans = max(ans,sum);文章来源地址https://www.toymoban.com/news/detail-681465.html
代码 :
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long LL;
int gcd(int a,int b){ return b==0 ? a : gcd(b,a%b); }
int lcm(int a,int b){ if(a==0||b==0) return 0; return (a*b)/gcd(a,b); }
bool is_prime(int x){if(x<2) return false;
for(int i=2;i<=x/i;i++) if(x%i==0) return false; return true;}
const int N = 2e5+10;
int n,x;
LL sum=0,ans = -1e9;
inline void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
sum += x;
ans = max(ans,sum);
if(sum < 0) sum = 0;
}
cout << ans << endl;
}
int main()
{
IOS
int _;
// cin >> _;
_ = 1;
while(_ --) solve();
return 0;
}
到了这里,关于秒懂算法2的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!