太戈编程第308题
暴力法
cin>>n>>m;
for(int i=0;i<n;i++) cin>>name[i]>>year[i];
for(int i=0;i<m;i++){
int x;
string y;
cin>>x>>y;
int OK=0;
for(int j=0;j<n;j++){
if(name[j]==y&&year[j]==x){
OK=1;
break;
}
}
cout<<OK<<" ";
}
这个算法复杂度为O(nm),显然有更快的算法
自定义类型
但是,这样写有个很危险的错误,如下
#include <bits/stdc++.h>
using namespace std;
struct dog{
string name;
int year;
};
int main(){
set<dog> s;
dog a,b;
a.name="mike";a.year=2020;
b.name="wangcai";b.year=2019;
s.insert(a);
s.insert(b);
return 0;
}
运行出来是这样的,
原因很简单,因为set的功能是排序、去重,然而结构体排序要加上“.",所以会报错
改后代码,
#include <bits/stdc++.h>
using namespace std;
struct dog{
string name;
int year;
bool operator<(const dog&d)const {
if(year<d.year) return 1;
if(year>d.year) return 0;
if(name<d.name) return 1;
return 0;
}
};
int main(){
set<dog> s;
dog a,b;
a.name="mike";a.year=2020;
b.name="wangcai";b.year=2019;
s.insert(a);
s.insert(b);
return 0;
}
那么,回到原题,代码该怎么写呢?
#include <bits/stdc++.h>
using namespace std;
struct dog{
string name;
int year;
bool operator<(const dog&d)const {
if(year<d.year) return 1;
if(year>d.year) return 0;
if(name<d.name) return 1;
return 0;
}
};
int main(){
set<dog> s;
dog d;
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>d.name>>d.year;
s.insert(d);
}
for(int i=0;i<m;i++){
cin>>d.year>>d.name;
if(s.count(d)) cout<<"1";
else cout<<"0";
}
return 0;
}
太戈编程第1497题
无set
#include <bits/stdc++.h>
using namespace std;
const int N=100009;
struct student{
int id,score;
bool operator<(const student&b)const {
if(score>b.score) return 1;
if(score<b.score) return 0;
if(id<b.id) return 1;
return 0;
}
};
student f[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>f[i].score;
f[i].id=i;
}
sort(f+1,f+1+n);
for(int i=1;i<=n;i++){
cout<<f[i].id<<" "<<f[i].score<<endl;
}
return 0;
}
有set
#include <bits/stdc++.h>
using namespace std;
const int N=100009;
struct student{
int id,score;
bool operator<(const student&b)const {
if(score>b.score) return 1;
if(score<b.score) return 0;
if(id<b.id) return 1;
return 0;
}
};
int main(){
int n;
cin>>n;
set<student> s;
student x;
for(int i=0;i<n;i++){
cin>>x.score;
x.id=i+1;
s.insert(x);
}
set<student>::iterator it;
for(it=s.begin();it!=s.end();it++)
cout<<(*it).id<<" "<<(*it).score<<endl;
return 0;
}
当然这个代码也有高级版,但要升级到c++14,如下
//不推荐使用,OJ好像不行
#include <bits/stdc++.h>
using namespace std;
const int N=100009;
struct student{
int id,score;
bool operator<(const student&b)const {
if(score>b.score) return 1;
if(score<b.score) return 0;
if(id<b.id) return 1;
return 0;
}
};
int main(){
int n;
cin>>n;
set<student> s;
int x;
for(int i=0;i<n;i++){
cin>>x;
s.insert({i+1,x});
}
set<student>::iterator it;
for(it=s.begin();it!=s.end();it++)
cout<<(*it).id<<" "<<(*it).score<<endl;
return 0;
}
太戈编程第309题
大家认真敲代码15min,15min后开讲
文章来源:https://www.toymoban.com/news/detail-755882.html
#include <bits/stdc++.h>
using namespace std;
struct ren{
int x,id;
bool operator<(const ren&b)const{
if(x<b.x) return 1;
if(x>b.x) return 0;
if(id<b.id) return 1;
return 0;
}
};
int main(){
int n;
cin>>n;
set<ren> s;
set<ren>::iterator it;
ren d;
for(int i=1;i<=n;i++){
cin>>d.x;
d.id=i;
s.insert(d);
}
set<int> ok;
for(int i=1;i<=n;i++){
it=s.begin();
d.x=(*it).x+3;
d.id=(*it).id;
s.erase(it);
s.insert(d);
ok.insert(d.id);
}
cout<<n-ok.size()<<endl;
return 0;
}
希望这些对大家有用,三联必回文章来源地址https://www.toymoban.com/news/detail-755882.html
到了这里,关于Peter算法小课堂—自定义容器的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!