CCF 第一、二题

最小差值 另解

先对数据进行排序，求相邻数据的最小值

打酱油

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <stdio.h>
#include <iomanip>
using namespace std;
/*
    题目：
    用时：tomato *
    思路：
*/


int main()
{
    int n; // n <=300
    while (cin>>n)
    {
        int x = n / 10 ;
        int five = ( x / 5 ) * 2;
        int thr = (x % 5) / 3 ;
        cout << five+thr + x <<endl;
    }


    return 0;
}

工程做法：使用常量为了程序的通用性

/* CCF201709-1 打酱油 */  

#include <stdio.h>  

const int ONE = 1;  
const int TWO = 2;  
const int FIVE = 5;  
const int THREE = 3;  
const int PRICE = 10;  

int main(void)  
{  
    int n, group1, group2, group3;  

    scanf("%d", &n);  

    group1 = n / PRICE / FIVE;  
    group2 = (n - group1 * PRICE * FIVE) / PRICE / THREE;  
    group3 = (n - group1 * PRICE * FIVE - group2 * PRICE * THREE) / PRICE;  

    printf("%d
", group1 * (FIVE + TWO) + group2 * (THREE + ONE) + group3);  

    return 0;  
}  

分蛋糕

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <stdio.h>
#include <iomanip>
using namespace std;
/*
    题目：分蛋糕
    思路：
*/


int main()
{
    int n,k;
    int cake = 0;
    int part = 0;
    int num = 0;
    while (cin>>n>>k)
    {
        while (n--)
        {
           cin >> part;
           cake += part;
           if (cake >= k )
           {
               cake = 0 ;
               num ++;
           }
        }
        if (cake < k )
        {
            num ++;
        }
        cout << num <<endl;
    }


    return 0;
}

100分答案：

#include <iostream>
using namespace std;

int main()
{
    int n, k, ans = 0, s = 0, a;
    cin >> n >> k;
    while (n--)
    {
        cin >> a;
        s += a;
        if (s >= k)
        {
            s = 0;
            ans++;
        }
    }
    if (s)ans++;
    cout << ans;
    return 0;
}

第一次做的只有20分，经过改进发现，if (cake)不要写成 if （cake < k ）,因为如果是刚刚好，cake应该为0，大于0的话才是蛋糕不够的的情况。要注意边界问题
另外能不使用数组而使用一次性变量的情况就使用变量，这不浪费内存呢么？

中间数

* 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <stdio.h>
#include <iomanip>
using namespace std;
/*
    题目：分蛋糕
    思路：
*/

bool equals(int a[],int n,int mid)
{
    int lit = 0;
    int big = 0;
        for (int i = 0 ;i < (n-1)/2 ; i++)
    {
        if (a[i] < mid)
            lit++;
    }
    for (int i = (n-1)/2+1 ;i < n ; i++)
    {
        if (a[i] > mid)
            big++;
    }
    if (lit == big)
        return true;
}

int main()
{
    int n;
    int a[1000];
    bool flag = 1;
    while ( cin  >>  n )
    {
        for (int i = 0;i<n;i++)
            cin >> a[i];

        sort(a,a+n);
        if ( n % 2 != 0 )
    {
        int mid = a[(n-1)/2];
        if (equals(a,n,mid)){
            cout << mid <<endl;
            flag = 0;
        }

    }
    else
    {
        int mid1= a[(n-1)/2];
        int mid2= a[(n+1)/2];
        if (equals(a,n,mid1)){
            cout <<mid1 <<endl;
            flag = 0;
        }
         else
            if (equals(a,n,mid2))
            {
                cout <<mid2<<endl;
                flag = 0;
            }
    }
    if (flag)
        cout << -1 <<endl;

    }

    return 0;
}

分数 ： 80
满分答案：减去与两侧相同的数

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <stdio.h>
#include <iomanip>
using namespace std;
/*
    题目：分蛋糕
    思路：
*/


const int N = 1000;
int a[N];
int main()
{
    int n;
    while ( cin  >>  n )
    {
        for (int i = 0;i<n;i++)
            cin >> a[i];

        sort(a,a+n);
        int mid = a[n/2];
        int left = n/2;
        int right = n - left - 1;
        for (int i = 0 ;i < n/2 ; i++)
            if (a[i] == mid )
                left -- ;
        for (int i = n/2+1 ;i < n; i++)
            if (a[i] == mid )
                right -- ;

        if (left == right)
            cout << mid <<endl;
        else
            cout << -1<<endl;
    }
    return 0;
}

最大波动

   * 不用数组，三个变量解决问题
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <stdio.h>
#include <iomanip>
using namespace std;
/*
    题目：
    思路：
*/

const int N = 1000;
int a[N];

int main()
{
    int n;
    int minN = 0;
    while (cin >>n)
    {
        for (int i=0;i < n;i++)
        {
            cin >> a[i];
        }
        for (int i = 0 ;i<n-1;i++)
        {
            if (abs(a[i+1] - a[i])> minN )
            {
                minN = abs(a[i+1]-a[i]);
            }
        }
        cout << minN <<endl;
    }
    return 0;
}
* 不需要使用数组的方法， 先输入第一个数，后面的数循环输入
int main(void)  
{  
    int n, first, second, delta, maxval=0;  

    // 输入n，输第１个数（从逻辑上来说应该写两句，为了简洁只需要写一句）  
    scanf("%d%d", &n, &first);  

    while(--n) {  
        //　输入第2至第n个数  
        scanf("%d", &second);  

        // 求差值（波动值），取绝对值，求最大值  
        delta = second - first;  
        if(delta<0)  
            delta = -delta;  
        maxval = MAX(maxval, delta);  

        first = second;  
    }  

    // 输出结果  
    printf("%d
", maxval);  

    return 0;  
}  

折点计数

*
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <stdio.h>
#include <iomanip>
using namespace std;
/*
    题目：
    思路：
*/


int main()
{
    // 求左边大右边大或左边小右边小的点的个数
    int n;
    int l, m ,r;
    int num = 0;
    while (cin >> n)
    {
        cin >>l>>m;
        for (int i=0;i<n-2;i++)
        {
            cin >> r;
            if ((l < m && r < m) || (l > m && r > m ))
                num ++;
            l = m; m = r;
        }
        cout << num <<endl;

    }
    return 0;
}

游戏

vector 没做出来，生气
1. 首先想到vector，注意vector的循环方法 迭代器+size（）判断
2. 使用erase的时候应当避免使用迭代器
3. 如果不使用STL，需要做一个变量标记

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#define maxSize 20
#define ERROR -1
using namespace std;
/*
     CCF ：2017-12-2
    Time : 游戏
    Date : 2018/3/14

*/
struct stu
{
    int num;
    int id;
};
int main()
{

    int n,k;
    stu s;
    int i;
    vector<stu>::iterator iter;
    while (cin>>n>>k)
    {
        vector<stu> vec;
        for (int i = 0 ;i < n ; i++)
        {
            s.id = i+1;
            vec.push_back(s);
        }


        int i = 0;
        while (vec.size() > 1)
        {
            for (iter = vec.begin(); iter != vec.end();i++)
            {
                iter->num = i+1;
                cout << "num :"<<iter->num<< "  id :"<<iter->id<<endl;

                if (iter->num%k == 0 || iter->num % 10 == k)
                {
                    cout << iter->id <<"号小朋友报数" << iter->num << "被淘汰" <<endl;
                    iter = vec.erase(vec.begin()+ iter->id - 1);
                }
                else
                    iter ++;

            }
        }
        cout << vec[0].id;

    }
    return 0;
}
* 正确：
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#define maxSize 20
#define ERROR -1
using namespace std;
/*
     CCF ：2017-12-2
    Time : 游戏
    Date : 2018/3/14

*/

int main()
{
    int n,k;
    cin >> n >> k;
    vector<int> vec;
    for (int i=0;i<n;i++)
        vec.push_back(i+1);
    int i = -1,no = 0;
    while (vec.size() > 1){
        no ++;
        i ++;
        i = i % vec.size(); // ★★★★ 相当于循环的作用
        if ( no % k == 0 || no % 10 == k)
        {
            vec.erase(vec.begin()+i);
            i--;
        }

    }
    cout << vec[0] <<endl;

    return 0;
}
* 从第一个进队的元素开始取，并pop（）弹出队列，如果no符合要求则不行动否则push（）到队列中。和学生的顺序无关？
 while(!q.empty()) {  
        head = q.front();  
        q.pop();  

        no++;  
        if(no % k == 0 || no % 10 == k)  
            ;  
        else  
            q.push(head);  
    }  
* 变量标记
const int N = 1000;  
bool flag[N];  

int main()  
{  
    int n, k;  

    // 读入数据  
    cin >> n >> k;  

    // 初始化  
    memset(flag, false, sizeof(flag));  

    // 模拟出局过程  
    int i = -1, no = 0, cnt = n;  
    while(cnt > 1) {  
        i++;  
        i %= n;  
        if(!flag[i]) {  
            no++;  
            if(no % k == 0 || no % 10 == k) {  
                flag[i] = true;  

                cnt--;  
            }  
        }  
    }   
    return 0;  
}  

ISBN

首先想到string，字符与整数的转化过程不要忘记！

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <stdio.h>
#include <iomanip>
#include <vector>
#include <queue>
using namespace std;
/*
    题目：ISBN号码
    思路：

*/


int main()
{
    string s;
    cin >> s;
    int c = 1;
    int sum = 0;
    for (int i = 0 ; i < s.length()-1 ;i ++)
    {
        if (s[i] != '-'){
            sum += (s[i]-'0')*c;
            c++;
        }
    }
    int c1 = sum % 11;
    char cc;
    // 逻辑上的错误！
    // 如果cc = x,不应该被认为是不正确的一类
    if (c1 == 10)
        cc = 'X';
    else
        cc = '0'+c1; // 统一转化为字符

    if ( cc == s[s.length()-1])
        cout << "Right" << endl;
    else
    {
        s[s.length()-1] = cc;
        cout <<s<< endl;
    }



    return 0;
}

窗口

窗口和点击操作用结构体实现，窗口从上到下的顺序用order数组表示，为了标记每个窗口的位置，给窗口结构体增加num序号，便于进行窗口移动的调整。

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <stdio.h>
#include <iomanip>
#include <vector>
#include <queue>
using namespace std;
/*
    题目：窗口
    思路：

*/
struct win{
    int x1;
    int y1;
    int x2;
    int y2;
    int no;
}win[11];

struct point
{
    int x;
    int y;
}point[11];
int order[11];


int belongToWin(int j,int x,int y)
{
    if ( (x >= win[j].x1 && x <= win[j].x2) &&(y >= win[j].y1 && y <= win[j].y2))
        return 1;
    else
        return 0;
}
void moveTo(int j,int n)
{
    // order中移动顺序
    int  t = order[j];
    for (int i = j ; i < n-1 ; i++ )
    {
        order[i] = order[i+1];
    }
    order[n-1] = t;
}
int main()
{
    int N,M;
    cin >> N >> M;
    int i;
    for (i = 0 ; i < N ;i++)
    {
        cin >> win[i].x1 >> win[i].y1 >> win[i].x2 >> win[i].y2;
        win[i].no = i+1;
        order[i] = i+1;
    }
    for ( i = 0 ; i < M ; i++)
    {
        cin >> point[i].x >> point[i].y ;
    }
    // 对point操作进行循环，每次找出位于最上层（order中大的）的窗口：改变order移动到最外层，输出窗口序号
    for ( i = 0 ;i < M ; i++)
    {
        bool flag = 1;

        for (int j = N-1 ; j >= 0 ; j--) // 从order的上层开始往下找符合点击范围内的
        {
            if (belongToWin(j,point[i].x,point[i].y))
            {
                if (j != N-1)
                {
                    // 不是最外层
                    moveTo(j,N); // 移动到最外层的函数
                }
                cout << win[order[N-1]-1].no <<endl;
                flag = 0;
                break;
            }
        }
        if (flag) // 都没点击到窗口内
            cout <<"IGNORED"<<endl;

    }



    return 0;
}
* 40 
// 判断哪个窗口被点击  
        for(int j=0; j<n; j++) {  
            if(win[order[j]].x1 <= point[i].x && point[i].x <= win[order[j]].x2 &&  
                    win[order[j]].y1 <= point[i].y && point[i].y <= win[order[j]].y2) {  
                // 得到窗口号  
                winno = win[order[j]].winno;  

                // 将被点击的窗口移到最前端  
                temp = order[j];  
                for(int k=j; k>0; k--)  
                    order[k] = order[k-1];  
                order[0] = temp;  

                break;  
            }  
        }  

        // 输出结果  
        if(winno == -1)  
            cout << "IGNORED" << endl;  
        else  
            cout << winno << endl;  
    }  

画图

矩阵用结构体表示，整个画布用数组表示

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <stdio.h>
#include <iomanip>
#include <vector>
#include <queue>
using namespace std;
/*
    题目：
    思路：

*/
const int N = 101;
struct rec
{
    int x1,y1,x2,y2;
}rec[N];

int paper[N][N] ;
// memset(paper,1,sizeof(paper))

int main()
{
    int n;
    int i,j,k;
    cin >> n ;
    for ( i = 0 ;i < n ; i++)
    {
        cin >> rec[i].x1 >> rec[i].y1 >> rec[i].x2>>rec[i].y2;
    }
    for (i = 0 ; i < N ; i++)
        for (j = 0 ; j < N ;j ++)
            paper[i][j] = 0;

    for (i = 0 ;i < n ;i++)
    {
        for ( j = rec[i].x1 ; j < rec[i].x2 ; j++)
            for ( k = rec[i].y1 ; k < rec[i].y2 ; k++)
        {
            paper[j][k] = 1;
        }
    }

    int num = 0;
     for (i = 0 ; i < N ; i++)
        for (int j = 0 ; j < N ;j ++)
            if (paper[i][j])
                num ++;

    cout << num <<endl;




    return 0;
}

数字排序

每个数字对应一个数量，使用map表示，一次循环输入，map自动排序
排序的工具使用优先队列，但需要创建对应Node结点和cmp函数，自定义优先队列的使用规则
优先队列特殊：大堆输出，所以和正常的cmp函数要反着写

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <stdio.h>
#include <iomanip>
#include <vector>
#include <queue>
#include <map>
using namespace std;
/*
    题目：
    思路：
    1.出现次数递减
    2. 出现次数相同时，先输出值小的

    1. 使用map进行统计
    2. 使用优先队列进行排序

*/
struct Node
{
    int val,c ;
};

struct cmp{
    bool operator()(Node a, Node b){
        if(a.c == b.c)  return a.val>b.val;
        return a.c < b.c;
    }
};
int main()
{
    int n;
    cin >> n;
    map<int,int> m ;
    int t;
    // 1.输入数据统计出现次数
    for (int i = 0; i < n ; i++){
        cin >> t;
        m[t] += 1;
    }
    /*debug*/
    // 2. 利用优先队列进行排序
    // priority_queue<map<int,int>,vector<map<int,int>,cmp> q; 不能把map作为队列元素
    // 把map集合中的值一对一对取出，存入node中，插入队列
    priority_queue<Node,vector<Node>,cmp> q;
    Node no ;
    map<int,int>::iterator iter ;
    for (iter = m.begin() ; iter !=m.end() ; iter++)
    {
        no.val = iter->first ;
        no.c = iter->second ;
        q.push(no);
    }



    // print
    while(!q.empty()){
        cout<<q.top().val<<' '<<q.top().c<<endl;
        q.pop();
    }



    return 0;
}

公共钥匙盒

1. 钥匙盒用数组表示，存储钥匙ID，没有则为-1
2. 老师的时间、操作不同，对钥匙盒的改变也不同，需要创建坐标轴的元素改变结点Node并初始化，为了排序，使用优先队列存储Node结点，按照自定义排序规则排序。遍历优先队列。

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#define maxSize 20
#define ERROR -1
using namespace std;
/*
     CCF ：2017-12-2
    Time : 公共钥匙盒（模拟题）
    思路 ：
    1. 如果在时间坐标轴上标记，某个事件，还/拿，某把钥匙，定义为一个操作节点
    2. 使用优先队列对操作节点进行排序，时间优先，时间相同先还再取，操作相同钥匙号小的有限
    3. 遍历优先队列中的操作，定义钥匙盒数组，没有钥匙为-1，利用循环从小到大找空位

*/
const int K = 1001;
struct Node
{
    int key; // 钥匙ID
    int time; // 时间
    char op;// 还钥匙R，取钥匙G
    bool operator < (Node a) const
    {
        if (time != a.time)
        {
            return time > a.time ;
        }else if (op != a.op){
            return op < a.op;
        }
        else{
            return key > a.key ;
        }
    }

};

const int N1 = 10000;
int box[N1]; // 钥匙盒子

int main()
{
    int n,k,c; // n 个房间，k 个老师
    // 输入老师的信息
    cin >> n >> k ;

    // 初始化钥匙盒信息
    memset(box,0,N1);
    for (int i = 0 ; i < n ; i++)
        box[i] = i+1;

    // 初始化优先队列，放入取钥匙和拿钥匙操作节点
    Node a;
    int last;
    priority_queue<Node> p;
    for (int i = 0 ; i < k ; i++ )
    {
        cin >> a.key >> a.time >> last;
        a.op = 'G';
        p.push(a);
        a.time = last + a.time;
        a.op = 'R';
        p.push(a);

   }
   /*debug
   while (!p.empty())
   {
       a = p.top();
       cout << a.key << " ";
       p.pop();
   }
   */


    // 遍历优先队列
    while (!p.empty())
    {
        a = p.top();
        p.pop();
        if (a.op == 'G')
        {
            for (int i = 0; i<n;i++)
            {
                if (box[i] == a.key)
                {
                    box[i] = -1;
                    break;
                }
            }
        }
        if (a.op == 'R')
        {
            for (int i=0;i<n;i++)
            {
                if (box[i] == -1)
                {
                    box[i] = a.key;
                    break;
                }
            }
        }
    }

    // print
    for (int i = 0 ; i< n-1;i++)
    {
        cout << box[i] << " ";
    }
    cout <<box[n-1]<<endl;






    return 0;
}

学生排队

vector 出队erase，入队insert，注意的是这两者的具体函数规则

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#define maxSize 20
#define ERROR -1
using namespace std;
/*
     CCF ：
    Time :
    思路 ：

*/
void print(vector<int> vec)
{
        for (int i= 0;i<vec.size();i++)
    {
        cout <<vec[i]<<" ";
    }
}

int main()
{
    int n;
    cin >>n;
    int m;
    cin >> m;
    int p,q;

    // 构造队列
    vector<int> vec;
    for (int i=0;i<n;i++)
    {
        vec.push_back(i+1);
    }

    vector<int>::iterator iter;
    for (int i= 0;i<m;i++)
    {
        cin >>p >>q;
        // 对队列进行操作
        for (iter =vec.begin() ; iter !=vec.end();iter++)
        {
            if (*iter == p)
                break;
        }
        if (++iter != vec.end())
        {
            vec.erase(--iter);
//print(vec);
            vec.insert(iter+q,p);
     //       print(vec);
        }
        else
        {
            vec.pop_back();
       //     print(vec);
            iter = vec.end();
            vec.insert(iter+q,p);
         //   print(vec);
        }
    }

    // print
    for (int i= 0;i<vec.size();i++)
    {
        cout <<vec[i]<<" ";
    }

    return 0;
}

工资计算

分段问题：正着好求，反着则先正着创建一个表格，然后通过表格找到大致范围，然后推回去。

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#define maxSize 20
#define ERROR -1
using namespace std;
/*
     CCF ：
    Time :
    思路 ：

*/
int gal[10]={0,1500,4500,9000,35000,55000,80000};
float tax[10] ={0,0.03,0.1,0.2,0.25,0.3,0.35,0.45};
int sal[11]={0,3500,4955,7654,11253};
int main()
{
    float t;
    cin >>t;
    float a = t - 3500; // 收税工资部分

    float sum = 3500;
    for (int i=1;i<7 ;i++)
    {
        sum += (gal[i]-gal[i-1])*(1-tax[i]);
        sal[i+1] = sum;
    }
  //  for (int i = 0;i<8;i++)
 //  cout << sal[i]<<endl;
    float sum2 = 3500;
    for (int i = 1;i<8;i++)
    {
        if (t<sal[i] && t>sal[i-1])
        {
            a = (t-sal[i-1])/(1-tax[i-1]);
            sum2 += a;
            sum2+=gal[i-2];
        }
        if ( t > sal[7])
        {
            a = (t-sal[7])/(1-tax[7]);
            sum2 +=gal[6];
        }
    }
    cout << (int)sum2 << endl;








    return 0;
}

60

/* CCF201612-2 工资计算 */  

#include <iostream>  

using namespace std;  

//#define DEBUG  

int salaryrange[] = {3500, 3500+1500, 3500+4500, 3500+9000, 3500+35000, 3500+55000, 3500+80000 };   
// 税前工资的范围
int taxrate[] = {3, 10, 20, 25, 30, 35, 45};  
const int SIZE = sizeof(salaryrange) / sizeof(int); 
// 定义长度不定的数组时计算size的方法 

int range[SIZE];  

int main()  
{  
    int t, s;  

    // 计算税后工资范围   
    range[0] = salaryrange[0];  
    for(int i=1; i<SIZE; i++) {  
        range[i] = range[i-1] + (salaryrange[i] - salaryrange[i-1])  
                - (salaryrange[i] - salaryrange[i-1]) * taxrate[i-1] / 100;  
    }  

#ifdef DEBUG  
    for(int i=0; i<SIZE; i++)  
        cout << range[i] << " ";  
    cout << endl;  
#endif  

    // 输入数据：  
    cin >> t;  

    // 计算收入范围  
    int i;  
    for(i=0; i<SIZE; i++)  
        if(t <= range[i])  
            break;  

    // 计算税前工资  
    if(i == 0)  
        s = t;  
    else {  
        s = salaryrange[i-1] + (t - range[i-1]) * 100 / (100 - taxrate[i-1]);  
    }  

    // 输出结果  
    cout << s << endl;  

    return 0;  
}  

消除游戏

对于数组的灵活使用，两个数组，一个是变量标记数组

* CCF201512-2 消除游戏 */  

#include <stdio.h>  
#include <string.h>  

#define N 30  

int a[N][N], t[N][N];  

int main(void)  
{  
    int n, m, i, j;  

    scanf("%d%d", &n, &m);  
    for(i=0; i<n; i++)  
        for(j=0; j<m; j++)  
            scanf("%d", &a[i][j]);  

 // 对二维数组的灵活运用
    memset(t, 0, sizeof(t));  
    // 进行行标记（可以消除则置1）  
    for(i=0; i<n; i++)  
        for(j=0; j<m-2; j++)  
            if(a[i][j]== a[i][j + 1] && a[i][j + 1] == a[i][j +2])  
                t[i][j] = t[i][j + 1] = t[i][j + 2] = 1;  
    // 进行列标记（可以消除则置1）  
    for(j=0; j<m; j++)  
        for(i=0; i<n-2; i++)  
            if(a[i][j] == a[i + 1][j] && a[i + 1][j] == a[i + 2][j])  
                t[i][j] = t[i + 1][j] = t[i + 2][j] = 1;  

    // 重置矩阵a  
    for(i=0; i<n; i++)  
        for(j=0; j<m; j++)  
            if(t[i][j])  
                a[i][j] = 0;  

    // 输出结果  
    for(i=0; i<n; i++) {  
        for(j=0; j<m; j++) {  
            if(j != 0)  
                printf(" ");  
            printf("%d", a[i][j]);  
        }  
        printf("
");  
    }  

    return 0;  
}  

火车购票

#include <iostream>
#include <map> 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
// 火车购票问题
 using namespace std;
 const int LINE = 20;
 const int NUM = 5;
int main(int argc, char** argv) {
    int n,v,start,end,j;
    cin >> n ;
    // 一行的座位打包，记录行数以及这行的剩余位置数 
    map<int ,int> m;
    // m初始化
    map<int,int>::iterator iter;
    for (int i = 1 ;i <= LINE ; i++ )
    {
        m[i] = NUM ;  
     } 
    for (int i = 0 ; i < n ; i++)
    {
        cin >> v; 
        // 1. 一行内满足购票
        // 逻辑：优先从小选择一行内的票，一行内从小到大排列 
        for (iter = m.begin() ; iter != m.end() ; iter ++)
        {
            if ( iter->second >= v )
            {
                // 分配座位，输出
                start = (iter->first - 1) * NUM + NUM - iter->second + 1;
                end = start + v - 1 ; 
                for (j = start ; j < end;j++)
                {
                    cout << j <<" ";
                }
                cout << end << endl;
                // 是否要删除座位 
                if (iter->second == v )
                {
                    m.erase(iter);
                }else
                {
                    iter->second = iter->second - v;
                }
                v = 0 ;
                break; 
            }
        }
        // 2.多行购票  需要判断是不是最后一个 
        bool isend = false; 
        while (v > 0)
        {
            for (iter = m.begin() ; iter!=m.end();iter ++){
                if (iter->second >= v ) 
            {
                    // 分配座位，输出
                start = (iter->first - 1) * NUM + NUM - iter->second + 1;
                end = start + v - 1 ; 
                for (j = start ; j < end;j++)
                {
                    cout << j <<" ";
                }
                if (!isend) 
                    cout << end << " ";
                else
                {
                    cout << end << endl;
                    isend = true;
                }
                // 是否要删除座位 
                if (iter->second == v )
                {
                    m.erase(iter);
                }else
                {
                    iter->second = iter->second - v;
                }

            }else 
            {
                start = (iter->first - 1) * NUM + NUM - iter->second + 1;
                end = start + iter->second - 1 ; 
                for (int j = start ; j <= end;j++)
                {
                    // 一定没有结束 
                    cout << j <<" ";
                }   
                v = v - iter->second; 
                // 要删除座位 
                m.erase(iter);  
            }   
            } 

        }

     } 
    return 0;
}

俄罗斯方块

coard 记录方格的具体位置，这样不用就4*4遍历了

#include <iostream>
#include <map> 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

 using namespace std;

const int ROW = 15;  
const int COL = 10;  
const int N = 4;  

int board[ROW+1][COL];  
int block[N][N];  
struct {  
    int row, col;  
} coords[N];

int main(int argc, char** argv) {

     int row, col;  

    // 输入数据  
    for(int i=0; i<ROW; i++)  
        for(int j=0; j<COL; j++)  
            cin >> board[i][j];  
    for(int i=0; i<N; i++)  
        for(int j=0; j<N; j++)  
            cin >> block[i][j];  
    cin >> col;  

    // 底边全放1  
    for(int j=0; j<COL; j++)  
        board[ROW][j] = 1;  

    // 提取小方块坐标  
    int k = 0;  
    for(int i=N-1; i>=0; i--)  
        for(int j=0; j<N; j++)  
            if(block[i][j] == 1) {  
                coords[k].row = i;  
                coords[k].col = j;  
                k++;  
            }  
    // 模拟小方块落下过程  
    row = 1;  
    col--;  // 第i列表示的是数组中的i-1 
    bool checkflag;  
    for(;;) {  
        checkflag = false;  

        for(int i=0; i<N; i++)  
            if(board[row + coords[i].row][col + coords[i].col] == 1) {  
                checkflag = true;  
                break;  
            }  

        if(checkflag)  
            break;  

        row++;  
    }  
    row--;  // 如果再往下一行会接触到1，就需要上移一行；或者是到了最底层 

    // 合并小方块到方格  
    for(int i=0; i<N; i++)  
        board[row + coords[i].row][col + coords[i].col] = 1;  

       // 输出结果  
    for(int i=0; i<ROW; i++) {  
        for(int j=0; j<COL; j++) {  
            if(j != 0)  
                cout << " ";  
            cout << board[i][j];  
        }  
        cout << endl;  
    }  
    return 0;
}