题意：少林武僧，每位武僧都有唯一的编号和唯一的战斗力值，每位新武僧都要与一位战斗力值最相近的老武僧比试（编号越大入寺时间越晚），求所有比试的记录；
#include<bits/stdc++.h> using namespace std; map<int,int> m; set<int> s; int main() { int n; while(scanf("%d",&n),n) { m.clear(); s.clear(); m[1e9]=1;//map记录战斗力值对应的id s.insert(1e9);//set保存战斗力值，并实现排序功能 for(int i=1;i<=n;i++) { int x,y; scanf("%d%d",&x,&y); set<int>::iterator it=s.lower_bound(y);//在老武僧战斗值序列中找到第一个大于等于新武僧战斗力的迭代器 printf("%d ",x);//新武僧id if(it==s.end())//it指向set的尾部迭代器，序列中不存在大于等于y的值，it--为最相近的战斗力值 { it--; printf("%d\n",m[*it]); } else //否则 { if(it==s.begin()) printf("%d\n",m[*it]); else { set<int>::iterator it1=it; it1--; if(abs(y-*it)<abs(y-*it1))//找到最近且最小的值 printf("%d\n",m[*it]); else printf("%d\n",m[*it1]); } } m[y]=x; s.insert(y); } } }
//stl容器
题意：找k个整数符合n1+n2+...nk=s,n1*n2*..*nk=p；
#include<bits/stdc++.h> using namespace std; int main() { int s,p,k,flag=0; cin>>s>>p>>k; if(k==1) { if(s==p)flag=1; } if(k==2) { for(int i=1;i*i<=p;i++) { if(p%i==0&&i+p/i==s)flag=1; } } if(k==3) { for(int i=1;i*i<=p;i++) { if(p%i!=0) continue; int d=p/i; for(int j=i;j*j<=d;j++) { if(d%j==0&&i+j+d/j==s)flag=1; } } } if(k==4) { for(int i=1;i*i<=p;i++) { if(p%i!=0) continue; int d=p/i; for(int j=i;j*j<=d;j++) { if(d%j!=0)continue; int e=d/j; for(int z=j;z*z<=e;z++) if(e%z==0&&i+j+z+e/z==s)flag=1; } } } if(flag)cout<<"YES\n"; else cout<<"NO\n"; }
//k的层数少，直接穷举方法
题意：0指令，设置矩阵大小，1指令，在（x，y）上加a；2指令，查询（l，b，r，t）对应矩阵区域上的手机数，3指令退出
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll num[1050][1050]; void init() { int x; scanf("%d",&x); memset(num,0,sizeof(num)); } void update(int x,int y,int a) { int temp=y; for(x;x<1050;x+=x&-x) { for(y=temp;y<1050;y+=y&-y) { num[x][y]+=a; } } } ll getsum(int x,int y) { ll ans=0; int temp=y; for(x;x>0;x-=x&-x) { for(y=temp;y>0;y-=y&-y) { ans+=num[x][y]; } } return ans; } int main() { int n; while(~scanf("%d",&n)) { if(n==3)break; if(n==0)init(); if(n==1) { int x,y,a; scanf("%d%d%d",&x,&y,&a); update(x+1,y+1,a); } if(n==2) { int l,b,r,t; scanf("%d%d%d%d",&l,&b,&r,&t); long long sum=getsum(r+1,t+1)+getsum(l,b)-getsum(r+1,b)-getsum(l,t+1); printf("%lld\n",sum); } } }
//二维树状数组
题意：n人凑钱买礼物，在追求公平的情况下尽可能的让钱多的人出钱
#include<bits/stdc++.h> using namespace std; struct node{ int id,money,cost; }a[105]; void init() { for(int i=1;i<=100;i++) a[i].id=a[i].money=a[i].cost=0; } int cmp(node x,node y) { return x.money>y.money||x.money==y.money&&x.id<y.id; } int cmp1(node x,node y) { return x.id<y.id; } int main() { int t; scanf("%d",&t); while(t--) { init();//初始化 int costsum,n; scanf("%d%d",&costsum,&n); int sum=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i].money); sum+=a[i].money; a[i].id=i; } if(sum<costsum)//总钱数不足以支付买礼物的费用 { printf("IMPOSSIBLE\n"); continue; } sort(a+1,a+n+1,cmp);//排序，按金钱额降序排序 int human=n; while(costsum) { if(costsum/human) { int ave=costsum/human,realcut=0,humancut=0;//ave平均费用 for(int i=1;i<=human;i++) { if(a[i].money-a[i].cost>ave) a[i].cost+=ave,realcut+=ave;//土豪余钱足以支付ave else realcut+=a[i].money-a[i].cost,a[i].cost=a[i].money,humancut++;//不足以支付ave，则有多少付多少 } human-=humancut;//humancut为无法参与下一轮费用分摊的人数 costsum-=realcut;//在本轮分摊费用中，实际分摊值 } else//剩余的钱不够剩余的土豪分摊 { for(int i=1;i<=costsum;i++)//位列前costsum的土豪各分担一美分 a[i].cost++; break; } } sort(a+1,a+n+1,cmp1);//按编号排序 for(int i=1;i<=n;i++) { if(i!=1)printf(" "); printf("%d",a[i].cost);//输出规划好的花费 } printf("\n"); } }
//贪心
题意：n个人，相互之间形成树形的关系，每个人有自己的快乐度，当他的直属上司不在时，快乐度生效，求快乐度的最大值
#include<bits/stdc++.h> using namespace std; int x,y,n,dp[6005][2],node,father[6005],son[6005],vis[6005]; void init() { memset(dp,0,sizeof(dp)); memset(vis,0,sizeof(vis)); memset(son,0,sizeof(son)); } void dfs(int root) { vis[root]=1; for(int i=1;i<=n;i++) { if(vis[i]==0&&father[i]==root) { dfs(i); dp[root][1]+=dp[i][0]; dp[root][0]+=max(dp[i][1],dp[i][0]); } } } int main() { while(~scanf("%d",&n)) { init();//初始化 for(int i=1;i<=n;i++) { scanf("%d",&dp[i][1]);//dp[i][1]表示当第i人参加聚会时快乐度的最大值 } while(scanf("%d%d",&x,&y),x||y) { father[x]=y;//x的父结点 son[x]++; } for(int i=1;i<=n;i++) { if(son[i]==0)//从根结点开始 { dfs(i); printf("%d\n",max(dp[i][1],dp[i][0])); break; } } } }
//树形DP
题意：求范围内符合双素数条件的个数
#include<bits/stdc++.h> using namespace std; const int Max=100005; int f[Max],num[Max]; void init() { f[0]=f[1]=1;int sum=0; for(int i=2;i<Max;i++) { if(f[i]==0) { if(f[i-2]==0)sum++; for(int j=i*2;j<Max;j+=i) { f[j]=1; } } num[i]=sum; } } int main() { init(); int n; while(scanf("%d",&n),n>=0) { printf("%d\n",num[n]); } }
//求素数
#include<bits/stdc++.h> using namespace std; struct node { int id,num; }a[50]; int cmp(node x,node y) { return x.num<y.num; } int main() { int t,n; scanf("%d",&t); for(int j=1;j<=t;j++) { scanf("%d",&n); for(int i=1;i<=n;i++) { int x; scanf("%d",&x); a[i].id=i; a[i].num=x; } sort(a+1,a+n+1,cmp); int sum=0; for(int i=1;i<=n;i++) { sum+=abs(a[i].id-i); } printf("Case #%d: %d\n",j,sum/2); } }
//排序
原文：https://www.cnblogs.com/llhsbg/p/11785011.html