太戈编程第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后开讲
#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;
}希望这些对大家有用，三联必回
