（复习次数：1）【HDU 1029】Ignatius and the Princess IV

http://acm.hdu.edu.cn/showproblem.php?pid=1029
注意，快读函数也不一定快，这里不如scanf
要意识到过半的数就是中位数

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#define INF 0x7fffffff
#define N 1000000
using namespace std;
//要意识到这个数就是中位数？？？ 
//可以与dp无关 
inline int read(){
    int x=0;char c=getchar();bool flag=0;while(c<'0'||c>'9'){
    if(c=='-')flag=1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}if(flag)x=-x;return x;
}
int a[N] ;
int main()
{
    int n;while(~scanf("%d",&n)){
    for(int i=0;i<n;i++){
    //scanf("%d",&a[i]);a[i]=read();}sort(a,a+n);printf("%d\n",a[(n+1)/2]);}return 0;
} 

法2：map stl

#include<cstdio>
#include<string.h>
#include<algorithm>
#include<map> 
using namespace std;
map<int,int>vis;//注意不能用char*,因为是指针，地址不会变的，不能count 
//可以试试string 
int main()
{
    int n;while (~scanf("%d",&n)){
    //记得把map清空！！！重复错vis.clear(); int flag=1;int out=(n+1)/2;for(int i=1;i<=n;i++){
    int m;scanf("%d",&m);if(flag){
    vis[m]+=1;if(vis[m]>=out){
    printf("%d\n",m);flag=0;						}}}}return 0;
}

法三，string，不行

#include<cstdio>
#include<string.h>
#include<algorithm>
#include<map> 
#include<string>
#include<iostream> 
#include<sstream>
using namespace std;
map<string,int>vis;//注意不能用char*,因为是指针，地址不会变的，不能count 
//可以试试string 
int main()
{
    int n;while (~scanf("%d",&n)){
    //记得把map清空！！！重复错vis.clear(); int flag=1;int out=(n+1)/2;for(int i=1;i<=n;i++){
    string s;stringstream ss;//以十六进制记录，并且不是原数 （很可能是指针），不能直接这么输出 （这体现的是int,stringstream,string的转化方法）int m;scanf("%d",&m);ss<<m;ss>>s;//不能cin>>m;是到\n结束 if(flag){
    vis[s]++;if(vis[s]>=out){
    cout<<s<<endl;flag=0;						}}}}return 0;
}
//结果：样例正确，超时 

复习：
5/18
贼简单。。
1.语法
/*法二：
for(auto i=m.begin();i!=m.end();i++){
printf("%d %d\n",i->first,i->second);
if(i->second>(n-1)/2){
ans=i->first;break;
}
}
法三：auto直接写作map<int,int>::iterator 类型
*/
2.
map注意置空 ，或开局部
因此wa了一次

#include<bits/stdc++.h>//<bits\stdc++.h>其实是一样的也可以！！ 
#ifdef LOCAL
FILE*FP=freopen("text.in","r",stdin);
#endif
using namespace std;
map<int,int>m;
signed main(){
    int n;while(~scanf("%d",&n)){
    int te,ans;for(int i=0;i<n;i++){
    scanf("%d",&te);if(++m[te]>(n-1)/2)ans=te;}/*法二： for(auto i=m.begin();i!=m.end();i++){printf("%d %d\n",i->first,i->second);if(i->second>(n-1)/2){ans=i->first;break;}}法三：auto直接写作map<int,int>::iterator 类型 */printf("%d\n",ans);m.clear();//注意置空 ，或开局部 }return 0;
}

复习上面：
但是数据强了，map可能超时！！
如果看出是中位数，那才是妙
但是我想要多思考一下的话应该能想到

#include<bits/stdc++.h>
using namespace std;
int a[1000000];
int main(){
    int n;while(~scanf("%d",&n)){
    for(int i=0;i<n;i++){
    scanf("%d",&a[i]);}sort(a,a+n);printf("%d\n",a[(n+1)/2]);}return 0;
}