洛谷 P1080 [NOIP2012 提高组] 国王游戏 P1842 [USACO05NOV] 奶牛玩杂技 刷题笔记

P1842 [USACO05NOV] 奶牛玩杂技 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P1080 [NOIP2012 提高组] 国王游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这两题大差不差

这俩题都有一个特点 即中间的相邻两项交换位置

对这两项之后的计算结果没有影响?

我们讨论这两项是否交换位置对结果大小的影响得到一个解决方案

然后将整体不断分成两项 两项即可解决问题?

对于奶牛玩杂技 ，

所以将牛按wi和si的和从小到大排序即可；

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;

struct Range
{
? ? int w, s;
? ? bool ?operator<(const Range &W)const // 按照总和从小到大排序
? ? {
? ? ? ? return (w + s) < (W.w + W.s);
? ? }
}range[N];

int main()
{
? ? scanf("%d", &n);
? ? for(int i = 1; i <= n; i ++ ) scanf("%d%d", &range[i].w, &range[i].s);

? ? sort(range + 1, range + 1 + n);
? ? // for(int i = 1; i <= n; i ++ ) printf("%d %d\n", range[i].w, range[i].s);

? ? for(int i = 1; i <= n; i ++ ) range[i].w += range[i - 1].w; // 求w的前n项和

? ? int res = -2e9;
? ? for(int i = 1; i <= n; i ++ ) res = max(res, range[i - 1].w - range[i].s); // 求最大的代价
? ? cout << res << endl;
? ? return 0;
}

对于国王游戏也可以进行类似分析

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
struct node{
?? ?int a;int b;
?? ?bool operator <(const node&Y)const {
?? ??? ?return a*b<Y.b*Y.a;
?? ?}
}a[N];
int sum[N];
int main(){
?? ?int n;
?? ?cin>>n;
?? ?//cin>>a[0].a>>a[0].b ;?
?? ?for(int i=0;i<=n;i++){
?? ??? ?cin>>a[i].a >>a[i].b ;
?? ?}
?? ?sort(a+1,a+1+n);
?? ?for(int i=0;i<=n;i++){
?? ??? ?//cout<<a[i].a <<' '<<a[i].b <<endl;
?? ?}
?? ?int maxx=a[0].a /a[0].b ;
?? ?sum[0]=a[0].a; ?
?? ?for(int i=1;i<=n;i++){
?? ??? ?sum[i]=sum[i-1]*a[i].a ;
?? ??? ? if(sum[i-1]/a[i].b >maxx){
?? ??? ? ?? ?maxx=sum[i-1]/a[i].b ;
?? ??? ? }
?? ?}
?? ?cout<<maxx;
?? ?return 0;
}

当然这么做只有60分还有40分需要使用高精度算法 ，我就不在这里讨论了。