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.

POJ 1979 POJ 3009 AOJ 0033 AOJ 0118 [搜索类题目][0033贪心模拟]

/** POJ 1979 BFS */ #include <stdio.h> #include <string.h> #include <iostream> #include <queue> using namespace std; const int N = 20 + 5; int mp[N][N]; int sx,sy; int n, m; int vis[3000]; int dirx[] = {0, 1, 0, -1}; int diry[] = {

hdu 4915 Parenthese sequence (贪心+模拟)

题目大意: 一个序列中有左括号和右括号,还有问号,问号可以任意转换成左右括号. 问这个序列有多少种情况的转变使得这个序列变成合法的括号匹配序列. 思路分析: 首先我们分析一下,如何使得一个序列是合法的括号匹配序列. 我们很容易想到的是用栈模拟匹配过程. 当遇到左括号就进栈,当遇到右括号就让栈顶的左括号出栈. 那么在模拟的过程中,造成这个序列的不合法的原因只有当右括号来的时候,此时的栈已经为空. 这里补充一句,一旦一个序列给定,那么这里面的问号有多少变成左括号,多少变成右括号,是一定的. 看完以上

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