1002 Game (贪心模拟)

1002 Game (贪心模拟)
Accepts: 572

Submissions: 6218

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Problem Description

度度熊在玩一个好玩的游戏。 游戏的主人公站在一根数轴上,他可以在数轴上任意移动,对于每次移动,他可以选择往左或往右走一格或两格。 现在他要依次完成 n 个任务,对于任务 i,只要他处于区间 [ai,bi]上,就算完成了任务。 度度熊想知道,为了完成所有的任务,最少需要移动多少次? 度度熊可以任意选择初始位置。

Input

第一行一个整数 T (1≤T≤10)表示数据组数。 对于每组数据,第一行一个整数 n (1≤n≤1000) 表示任务数。 接下来 n 行,第 iii 行两个整数 ai,bi (1≤ai≤bi≤1000000) 表示任务对应的区间。

Output

对于每组数据,一行一个整数表示答案。

Sample Input

1
2
1 10
20 30
Sample Output

5

样例描述
选取10为起点,经过的轨迹为10-12-14-16-18-20。

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int l,r;

int solve(int x,int y){
    int teml=max(x,l);
    int temr=min(y,r);
    if(teml<=temr){
        l=teml,r=temr;
        return 0;
    }
    else if(r<x){
        int res=(x-r+1)/2;
        l=x;
        if((x-r&1)&&x<y) r=x+1;
        else r=x;
        return res;
    }
    else if(l>y){
        int res=(l-y+1)/2;
        r=y;
        if((l-y&1)&&x<y) l=y-1;
        else l=y;
        return res;
    }

}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        ll ans=0;
        int m;
        scanf("%d",&m);
        l=1;r=1000000;
        while(m--){
            int x,y;
            scanf("%d%d",&x,&y);
            ans+=solve(x,y);
        }
        printf("%lld\n",ans);
    }
} 

这个代码太巧妙了

原文地址:https://www.cnblogs.com/ellery/p/11644992.html

时间: 10-09

1002 Game (贪心模拟)的相关文章

[贪心+模拟] zoj 3829 Known Notation

题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5383 Known Notation Time Limit: 2 Seconds      Memory Limit: 65536 KB Do you know reverse Polish notation (RPN)? It is a known notation in the area of mathematics and computer science.

UVA 11776 - Oh Your Royal Greediness! - [贪心/模拟]

题目链接:https://cn.vjudge.net/problem/UVA-11776 题意: 给出数字n(0<=n<=1000),代表有n个农民,接下来有n行,每行两个数字S和E代表这个农民工作时间为[S,E]: 每个农民工作时,需要有一个enforcer来监督,且每个enforcer一次只能监督一个农民: 求最少需要多少个enforcer. 题解: 这道题我也不太清楚算贪心还是算模拟,可能两者都有一点吧. 首先我们根据正常思维,既然要模拟分配监工去监督农民,那么肯定先给第一个开始做的农民

【BZOJ2457】[BeiJing2011]双端队列 贪心+模拟

[BZOJ2457][BeiJing2011]双端队列 Description Sherry现在碰到了一个棘手的问题,有N个整数需要排序. Sherry手头能用的工具就是若干个双端队列. 她需要依次处理这N个数,对于每个数,Sherry能做以下两件事: 1.新建一个双端队列,并将当前数作为这个队列中的唯一的数: 2.将当前数放入已有的队列的头之前或者尾之后. 对所有的数处理完成之后,Sherry将这些队列排序后就可以得到一个非降的序列. Input 第一行包含一个整数N,表示整数的个数.接下来的

FZU 2041 Checker (贪心+模拟)

题目地址: FZU 2041 这个题是昨天的队内选拔赛用的套题里的其中一道题,我当时想到方法了,但是没敢写..一个是对复杂度有些不确定,万一组数很多的话好像就会跪..而且感觉不太好实现,队里还卡着两道题,就打算等别的该出的题出了之后再写,结果没时间了.. 刚才按照那思路写了一下..结果就过了...真心醉了..我&--%¥%**--%% 思路是先枚举每个空隙,然后对该空隙向左向右贪心的一步步的去移动,剩下的就是小模拟了.然后找出所有空隙可能扩大的最大值就可以了. 代码如下: #include <

To Fill or Not to Fill(贪心模拟)

题目描述: With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are

贪心 模拟

贪心 Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u Description 杂货店出售一种由N(3<=N<=12)种不同颜色的颜料,每种一瓶(50ML),组成的颜料套装.你现在需要使用这N种颜料:不但如此,你还需要一定数量的灰色颜料.杂货店从来不出售灰色颜料——也就是它不属于这N种之一.幸运的是,灰色颜料是比较好配置的,如果你取出三种不同颜色的颜料各x ml,混合起来就可以得到x

hdu 4023 2011上海赛区网络赛C 贪心+模拟

以为是贪心,结果不是,2333 贪心最后对自己绝对有利的情况 点我 1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 #include<map> 8 using namespace std; 9 #define MOD 10000000

HDU 4023 (博弈 贪心 模拟) Game

如果硬要说这算是博弈题目的话,那这个博弈是不公平博弈(partizan games),因为双方面对同一个局面做出来的决策是不一样的. 我们平时做的博弈都是公平博弈(impartial games),所以在这道题里面,那些必胜必败状态,SG函数SG定理都派不上用场了. 但是,这道题是可以贪心的. 比如第一个图案对于Alice来说是安全稳定的,因为Bob不会跟他去抢位置,所以Alice可以省到最后去放.同样地,Bob可以将第2个图案省到最后再去放. 比如说第15个图案,如果能抢先占到的话会很划算的,

HDU 4708 Rotation Lock Puzzle (贪心+模拟)

Rotation Lock Puzzle Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1668    Accepted Submission(s): 530 Problem Description Alice was felling into a cave. She found a strange door with a number

UVA - 11054 Wine trading in Gergovia (Gergovia 的酒交易)(贪心+模拟)

题意:直线上有n(2<=n<=100000)个等距的村庄,每个村庄要么买酒,要么卖酒.设第i个村庄对酒的需求为ai(-1000<=ai<=1000),其中ai>0表示买酒,ai<0表示卖酒.所有村庄供需平衡,即所有ai之和等于0.把k个单位的酒从一个村庄运到相邻村庄需要k个单位的劳动力.计算最少需要多少劳动力可以满足所有村庄的需求. 分析:从最左面的村庄考虑,不管他是买酒还是卖酒,相对于他的相邻村庄都会有a0的运输量,所以运输量不断累加或抵消,一直算到最右边村庄即可.