admin管理员组文章数量:1622287
这道题就是解决选择策略问题。
思路一:
先将田忌跟齐王的马的速度数组进行一次冒泡排序
1、如果田忌最慢的马比齐王最慢的马快,则比慢马
2、如果田忌最慢的马比齐王最慢的马慢,则用田最慢的马跟齐最快的马比 //消耗齐的快马这是贪心的第一步
3、如果田忌最慢的马的速度与齐威王最慢的马速度相等
3.1、如果田忌最快马的比齐威王最快的快,则比快马 //这是贪心的第二步
3.2、如果田忌最快马比齐威王最快的慢,田忌慢VS齐王快
3.3、如果田忌最快马比齐威王最快的相等,田忌慢VS齐王快
#include<cstdio>
#include<algorithm>
using namespace std;
int a[1010],b[1010];
int main()
{
int n,i,awin,bwin,afast,bfast,aslow,bslow;
while(scanf("%d",&n)&&n)
{
for(i=0;i<n;++i)
scanf("%d",&a[i]);//tian的马
for(i=0;i<n;++i)
scanf("%d",&b[i]);
sort(a,a+n);//从小到大
sort(b,b+n);
awin=bwin=0;//记录赢的次数
afast=bfast=n-1;//标记最快的马
aslow=bslow=0;//标记最慢的马
for(i=0;i<n;++i)
{
if(a[aslow]>b[bslow]) //tian的慢马 大于 king的慢马
{
awin++; //tian胜利
aslow++; //tian的马
bslow++; //king的马
}
else if(a[aslow]<b[bslow]) //用最慢马消耗国王的最快马
{
bwin++; //king胜利
aslow++;
bfast--;
}
else//两匹最慢马速度相同时
{
if(a[afast]>b[bfast]) //tian的快马 大于 king的快马
{
awin++;
afast--;
bfast--;
}
else if(a[aslow]<b[bfast]) //如果田忌的最快马不能胜国王的最快马,则用慢马消耗
{
bwin++;
aslow++;
bfast--;
}
}
}
printf("%d\n",200*(awin-bwin));
}
return 0;
}
思路二:
先将田忌跟齐王的马的速度数组进行一次冒泡排序
1、如果田忌最快的马比齐王最快的马快,则快马比
2、如果田忌最快的马比齐王最快的马慢,则用田最慢的马跟齐最快的马比 //这是贪心的第一步
3、如果田忌最快的马的速度与齐威王最快的马速度相等
3.1、如果田忌最慢的比齐威王最慢的快,则慢马比 //这是贪心的第二步
3.2、如果田忌最慢的比齐威王最慢的慢,田忌慢VS齐王快(这里要判断田忌慢马和齐王快马速度是否相等)
3.3、田忌最慢的与齐威王最慢的相等,田忌慢VS齐王快(这里要判断田忌慢马和齐王快马速度是否相等)
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <stdio.h>
using namespace std;
bool compare(int a, int b) {
return a < b; //从小到大排序
}
int main() {
int n;
int sum = 0;
int tj[1000] = {0};
int gw[1000] = {0};
while (cin >> n && n) {
sum = 0;
tj[1000]={0};
gw[1000]={0};
for (int j = 0; j < n; j++) {
cin >> tj[j];
}
for (int j = 0; j < n; j++) {
cin >> gw[j];
}
sort(tj, tj + n, compare);
sort(gw, gw + n, compare);
int tj1 = 0, tj2 = n - 1;//比较指针
int gw1 = 0, gw2 = n - 1;
while (n--) {
if (tj[tj2] < gw[gw2]) { // 比国王的慢
gw2--;
tj1++;
sum=sum-200;
continue;
}
if (tj[tj2] > gw[gw2]) { // 比国王的快
gw2--;
tj2--;
sum=sum+200;
continue;
}
if (tj[tj2] = gw[gw2]) { // 和国王的一样
if(tj[tj1] <= gw[gw1]){ //田 最慢的比国王 最慢的 慢
if(tj[tj1] != gw[gw2]){ //注意:田忌慢马和齐王快马速度是否相等
sum=sum-200;
}
gw2--; //田用慢的比
tj1++;
continue;
}
if(tj[tj1] > gw[gw1]){ //田 最慢的比国王 最慢的 快
sum=sum+200;
tj1++; //田用快的比
gw1++;
continue;
}
}
}
cout << sum << endl;
}
return 0;
}
版权声明:本文标题:hdoj 1052 Tian Ji -- The Horse Racing 贪心算法 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1728851560a1176737.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论