Week 6 贪心算法
P1199 [NOIP2010 普及组] 三国游戏
-
知识点：贪心、博弈题
-
思路：计算机的选择是贪心的，所以玩家和计算机都不可能选到默契值最大的武将组合。
小涵赢的情况：在第二次选将时可以拿到第一次选中的武将的次大默契值组合。
#include<bits/stdc++.h>
using namespace std;
int a[501][501],n;
int main()
{
int m=0;
cin>>n;
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
cin>>a[i][j];
a[j][i]=a[i][j];
}
}
for(int i=1;i<=n;i++)
{
sort(a[i]+1,a[i]+n+1);
if(a[i][n-1] > m)
m= a[i][n-1];
}
cout<<"1"<<endl<<m;
return 0;
}
P1007 独木桥
-
思路：和之前写过的蚂蚁很像，两士兵碰头调转可以看成直接穿过士兵往前走（因为每个士兵没有差别
#include<bits/stdc++.h> using namespace std; int main() { int l,n,ma=0,mi=0; cin>>l>>n; while(n--) { int x; cin>>x; ma=max(ma,max(x,l+1-x)); mi=max(mi,min(x,l+1-x)); } cout<<mi<<" "<<ma<<endl; return 0; }
P1223 排队接水
-
知识点：贪心算法
-
思路：数组从小到大排序~
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
struct sz{
int t,num;
};
bool cmp(sz x, sz y)
{
return x.t <y.t;
}
int main()
{
int n;
double sum=0;
sz a[N];
cin>>n;
for(int i=1;i<=n;i++)
{
a[i].num =i;
cin>>a[i].t;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
cout<<a[i].num <<" ";
cout<<endl;
for(int i=1;i<=n;i++)
{
int j=n-i;
sum+=a[i].t *j;
}
printf("%.2f",sum/n);
return 0;
}
P1090 [NOIP2004 提高组] 合并果子
- 考点：贪心+优先队列
- 思路：每次合并最小的两堆即可
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,ans=0;
priority_queue<int,vector<int>,greater<int>> a;
cin>>n;
while(n--)
{
int x;
cin>>x;
a.push(x);
}
while(1)
{
int x=a.top();
a.pop();
if(a.empty())
break;
x+=a.top();
a.pop();
ans+=x;
a.push(x);
}
cout<<ans<<endl;
return 0;
}