admin管理员组文章数量:1621658
转自 https://wwwblogs/Open_Source/archive/2010/07/09/1904940.html
解题思路:贪心算法。根本思想是要让田忌花最小的代价来胜一每一场,让齐王花最大的代价来胜每一场。(“代价”可以用比较的两匹马的权值之差来形象地表示)
首先将两人的马排序。
(让田忌每一匹马实现自己的最大价值)这时如果田忌最劣的马是所有中最劣的,就让它跟齐王最强的比较(这时对于田忌的这匹劣马来说并不会比其它的情形坏,因为它注定要输)齐王的最强马没了,对于田忌其他马来说胜率更大,如果田忌最劣的马不是最劣的,说明这匹马强于齐王最劣的,那就让它们比较,让田忌胜出(按照贪心仔细想想,如果让每一匹马的价值最大,其实操作应该更加复杂,假设田忌最差的是t_low,速度为80,齐王最差的是k_low1,速度68,第二差的k_low2 速度79,如果需要价值最大化,应该用t_low去胜K_low2)(但是实际上并不需要,因为t_low2速度大于t_low1,前两场无论田忌怎么出t_low1和2一定胜,但是如果K_low3速度大于t_low3,最终还是2胜一败,虽然实现了最大价值,但是并没有改变结果)
原文:https://blog.csdn/lawrencesgj/article/details/8001638
*
贪心策略:
1,如果田忌的最快马快于齐王的最快马,则两者比。
(因为若是田忌的别的马很可能就赢不了了,所以两者比)
2,如果田忌的最快马慢于齐王的最快马,则用田忌的最慢马和齐王的最快马比。
(由于所有的马都赢不了齐王的最快马,所以用损失最小的,拿最慢的和他比)
3,若相等,则比较田忌的最慢马和齐王的最慢马
3.1,若田忌最慢马快于齐王最慢马,两者比。
(田忌的最慢马既然能赢一个就赢呗,而且齐王的最慢马肯定也得有个和他比,所以选最小的比他快得。)
3.2,其他,则拿田忌的最慢马和齐王的最快马比。
(反正所有的马都比田忌的最慢马快了,所以这匹马必输,选贡献最大的,干掉齐王的最快马)
我的是从最慢的马开始弄的....思路基本相同
#include<iostream>
# include<algorithm>
using namespace std;
int t[1000], k[1000];
int main(void) {
int n;
cin >> n;
while (n) {
for (int i = 0; i < n; i++)
cin >> t[i];//田的马
for (int i = 0; i < n; i++)
cin >> k[i];//王的马
sort(t, t + n);
sort(k, k + n);
int tlow, klow, tfast, kfast;
tlow = klow = 0;
tfast = kfast = n - 1;
int twin, kwin; twin = kwin = 0;
for (int i = 0; i < n; i++) {
if (t[tlow] < k[klow]) {//最差对王最强
tlow++; kfast--; kwin++;
}
else if (t[tlow] == k[klow]) {
//看快马
if (t[tfast] > k[kfast]) {
tfast--; kfast--; twin++;
}
else {//快马相等或者没有王快都是用慢马消耗
if (k[kfast] > t[tlow])kwin++;
tlow++; kfast--;
}
}
else {//田忌慢马赢
tlow++; klow++; twin++;
}
}
cout << (twin - kwin) * 200<<endl;
cin >> n;//下一轮
}
system("pause");
return 0;
}
下面是我的自检方法:之前一直AC不了,写了个自检来找错误案例
# include<iostream>
#include<algorithm>
#pragma warning (disable:4996)
using namespace std;
int t[1010], k[1010];
int R(void) {//伪随机自检
int randn= (rand() % 10) + 1;
for (int i = 0; i < randn; i++) {
t[i] = (rand() % 99 )+ 1;
k[i]= (rand() % 99) + 1;
}
return randn;
}
//正确答案
int Y(int n) {
int i, awin, bwin, afast, bfast, aslow, bslow;
sort(t, t + n);
sort(k, k + n);
awin = bwin = 0;//记录赢的次数
afast = bfast = n - 1;//标记最快的马
aslow = bslow = 0;//标记最慢的马
for (i = 0; i < n; ++i)
{
if (t[aslow] >k[bslow])
{
awin++;
aslow++; bslow++;
}
else if (t[aslow] < k[bslow])//用最慢马消耗国王的最快马
{
bwin++;
aslow++; bfast--;
}
else//两匹最慢马速度相同时
{
if (t[afast] > k[bfast])
{
awin++;
afast--; bfast--;
}
else if (t[aslow] < k[bfast])//如果田忌的最快马不能胜国王的最快马,则用慢马消耗
{
bwin++;
aslow++; bfast--;
}
}
}
return (awin - bwin) * 200;
}
//我的答案
int My(int n) {
int tlow, klow, tfast, kfast;
tlow = klow = 0;
tfast = kfast = n - 1;
int twin, kwin; twin = kwin = 0;
for (int i = 0; i < n; i++) {
if (t[tlow] < k[klow]) {//最差对王最强
tlow++; kfast--; kwin++;
}
else if (t[tlow] == k[klow]) {
//看快马
if (t[tfast] > k[kfast]) {
tfast--; kfast--; twin++;
}
else {//快马相等或者没有王快都是用慢马消耗
if (k[kfast] > t[tlow])kwin++;
tlow++; kfast--;
}
}
else {//田忌慢马赢
tlow++; klow++; twin++;
}
}
return (twin - kwin) * 200;
}
int main()
{
int nn,time=0;
while ((time++)<100000) {
cout << time << endl;
nn = R();
int yre = Y(nn);
int mre = My(nn);
if (yre != mre) {
for (int i = 0; i < nn; i++) {
cout << t[i] << " ";
if (!((i + 1) % 10))cout << endl;
}
cout << "出现答案不同的案例:" << endl;
cout << "--------------------------------";
cout << endl << nn << endl;
cout << "________正确答案:" << yre << endl;
cout << "________我的答案:" << mre << endl;
cout << "---------------------------------";
cout << endl << endl << endl;
for (int i = 0; i < nn; i++) {
cout << k[i] << " ";
if (!((i + 1) % 10))cout << endl;
}
system("pause");
}
}
system("pause");
return 0;
}
版权声明:本文标题:【 OJ 】 HDOJ1052 贪心模拟田忌赛马 [ 46 ] 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728850652a1176634.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论