避风港
0%

发表于 更新于 分类于 ，

什么是序列化？

所谓的序列化就是将对象流化，就是将对象变成字节。

如何实现序列化？

让某个类实现Serializable接口(标记性接口)。

将一个对象保存到文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//创建Student类
public class Student implements Serializable{ //实现标记性接口Serializable
    private String Num;
    private String Name;
    private String Sex;
    public Student(String Num,String Name,String Sex){
        this.Num = Num;
        this.Name = Name;
        this.Sex = Sex;
    }
}
public void objectToFile throws Exception{
     //创建对象流
     FileOutputStream fos = new FileOutputStream("X:\\xxx.xxx");
     ObjcetOutputStream oos = new ObjcetOutputStream(fos);
     //创建对象
     Student student1 = new Student("123","王五"，"男");
     //将对象写出
     oos.writeObject(student1);
     //关闭流(从外到内)
     oos.close();
     fos.close();
}

从文件中读取一个对象

1
2
3
4
5
6
7
8
9
10
11
12
public void readFromFile() throws Exception{
     //创建对象流
     FileInputStream fis = new FileInputStream("X:\\xxx.xxx");
     ObjectInputStream ois = new ObjectInputStream(fis);
     //读取对象
     Student student2 = (Student)ois.readObject();
     //输出对象
     System.out.println(student2);
     //关闭流(从外到内)
     ois.close();
     fis.close();
}

发表于 更新于 分类于 ，

字节输出流

1
2
3
4
5
6
7
8
9
10
11
12
13
public void writeFile() throws Exception{
      Scanner input = new Scanner(System.in);
      //将文件封装为File对象
      File file = new File("X:\\xxx.xxx");
      //输出数据
      String str = input.next();
      //字节输出流
      FileOutputStream fos = new FileOutputStream(file,true);
      //将代码数据保存到磁盘
      fos.write(str.getBytes());
      //关闭流
      fos.close();
}

字节输入流

1
2
3
4
5
6
7
8
9
10
11
12
13
public void readFile() throws Exception{
     //将文件封装为File对象
     File file = new File("X:\\xxx.xxx");
     建立磁盘通向程序代码的管道(字节输入流)
     FileInputStream fis = new FileInputStream(file);
     int len = 0;
     //读取数据
     while((len = fis.read()) != -1){
         System.out.print((char)len);
     }
     //关闭流
     fis.close();
}

(缓冲流)文件的复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void copyVideoQuik() throws Exception{
      //磁盘通往代码的管道
      FileInputStream fis = new FileInputSteam("X:\\xxx.xxx");
      //管道加粗
      BufferedInputSteam bis = new BufferedInputSteam(fis);
      //代码通往磁盘的管道
      FileOutputStream fos = new FileOutputStream("X:\\xxx.xxx");
      //管道加粗
      BufferedOutputStream bos = new BufferedOutputStream(fos);
      byte[] car = new byte[1024];//一次读取1024字节(速度最优)
      int len = 0;//len=-1代表读取结束
      while((len = bis.read(car)) != -1){
          //读取的数据保存到磁盘
         bos.write(car,0,len);//从car里读取，从下标0开始，读1024个
         //System.out.println(new String(car,0,len));//转字符串逐行打印
      }
      //关闭流：先关外管道流，再关内管道流
      //关输入流
      bis.close();
      fis.close();
      //关输出流
      bos.close();
      fos.close();
}

发表于 分类于

P2880 [USACO07JAN]Balanced Lineup G

题目背景

每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛. 但是为了避免水平悬殊,牛的身高不应该相差太大. John 准备了Q (1 <= Q <= 180,000) 个可能的牛的选择和所有牛的身高 (1 <= 身高 <= 1,000,000). 他想知道每一组里面最高和最低的牛的身高差别.

输入：

第1行：N,Q

第2到N+1行：每头牛的身高

第N+2到N+Q+1行：两个整数A和B，表示从A到B的所有牛。（1<=A<=B<=N）

输出：

输出每行一个数，为最大数与最小数的差

输入输出样例

输入 #1

1
2
3
4
5
6
7
8
9
10
6 3
1
7
3
4
2
5
1 5
4 6
2 2

输出 #1

1
2
3
6
3
0

经典RMQ(区间最值查询问题)，可以用线段树和树状数组实现，这里用ST表。在实现ST表前，需要先了解几个基本概念。

1
2
3
1.2^log(x)>x/2
2.2进制移位，如1<<n = 2^n
3.基本的dp思想

好的，现在开始——-
题目大意：给一个乱序数组，q个询问，问区间[l,r]上的最大值和最小值的差。

首先，我们用一个二维数组maxx[i][j]，记录从第i个数开始，长度为2^j的区间中的最大值。
很明显，当j=0时，maxx[i][0]记录的是从第i个数开始，长度为1的区间中的最大值，即a[i]自身。
因此，在输入a[i]时，顺便将maxx[i][0]初始化：

1
2
3
4
for (int i = 1; i <= n; i++) {
  cin >> a[i];
  maxx[i][0] = a[i];
}

那么，我们该如何求maxx[i][1]的值呢？

maxx[i][1]记录的是从i开始，长度为2^1的区间的最大值，也就是i和i+1的最大值，我们可写为max(i,i+1)，

肯定有人会发现，这里的i和i+1不就是maxx[i][0]和maxx[i+1][0]吗！

是的，我们也可以表示为max(maxx[i][0],maxx[i+1][0])，更进一步的，可以表示为max(maxx[i][0],maxx[i+(1<<0)][0]),

进一步地进行推导，我们可以得到：maxx[i][j] = max(maxx[i][j-1],maxx[i+(1<<(j-1))][j-1])。

解释一下：

我们要求从i开始，区间长度为2^j中的最大值，我们可以将2^j拆分为2个长度为2^(j-1)的区间，它们分别从i和i+2^(j-1)开始。

这两个区间最大值的最大值，就是最开始区间的最大值。即a~c的最大值 = max(a~b的最大值，b~c的最大值)。

1
2
3
for (int j = 1; 1<<j<=n; j++) 
        for (int i= 1; i + (1 << j) - 1 <= n; i++) 
            maxx[i][j] = max(maxx[i][j - 1], maxx[i+ (1 << (j - 1))][j - 1]);

注意点：

1.j的范围：要保证2^j<=n

2.i的范围：因为从i开始，区间长度为2^j的区间右界为i+2^j-1，所以i+2^j-1<=n

好了，处理完成，下一步是查找[l,r]上的最大值
这里就要用到我们之前提到的公式：2^log(x)>x/2。x是区间长度，那么用在这里就是：2^log(r-l+1)>(r-l+1)/2
那么，我们便可以将这个区间分为两段
第一段是从l开始，区间长度为2^log(r-l+1)，第二段从r-2^log(r-l+1)+1开始，到r结束。

1
2
3
4
5
for (int i = 1; i <= m; i++) {
         cin >> l >> r;
         int logg = log2(r-l+1);
         cout << max(maxx[l][logg], maxx[r - (1 << logg) + 1][logg]) << endl;;
     }

附上完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
int maxx[50011][51];
int minn[50011][51];
int a[50011];
int n, m;
int main() {
    int l, r;
    cin >> n>>m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        maxx[i][0] = a[i];
        minn[i][0] = a[i];
    }
    for (int i = 1; 1<<i<=n; i++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j++) {
            maxx[j][i] = max(maxx[j][i - 1], maxx[j + (1 << (i - 1))][i - 1]);
            minn[j][i] = min(minn[j][i - 1], minn[j + (1 << (i - 1))][i - 1]);
        }
    }
    for (int i = 1; i <= m; i++) {
        cin >> l >> r;
        int logg = log2(r-l+1);
        cout << max(maxx[l][logg], maxx[r - (1 << logg) + 1][logg]) - (min(minn[l][logg], minn[r - (1 << logg) + 1][logg])) << endl;;
    }
    return 0;
}

发表于 分类于

P2949 [USACO09OPEN]Work Scheduling G

题目描述

Farmer John has so very many jobs to do! In order to run the farm efficiently, he must make money on the jobs he does, each one of which takes just one time unit.

His work day starts at time 0 and has 1,000,000,000 time units (!). He currently can choose from any of N (1 <= N <= 100,000) jobs

conveniently numbered 1..N for work to do. It is possible but

extremely unlikely that he has time for all N jobs since he can only work on one job during any time unit and the deadlines tend to fall so that he can not perform all the tasks.

Job i has deadline D_i (1 <= D_i <= 1,000,000,000). If he finishes job i by then, he makes a profit of P_i (1 <= P_i <= 1,000,000,000).

What is the maximum total profit that FJ can earn from a given list of jobs and deadlines? The answer might not fit into a 32-bit integer.

输入格式

Line 1: A single integer: N

Lines 2..N+1: Line i+1 contains two space-separated integers: D_i and P_i

输入输出样例

输入 #1

3

2 10

1 5

1 7

输出 #1

17

预备知识：

1.贪心算法

2.用STL优先队列实现堆

3.关系运算符重载

思路：

先了解题目大意，每个单位时间可以完成一项工作，但每项工作都有各自的过期时间，过期的工作不能选择，求最大利润。

很明显，这题用到了贪心的思想，要在所给的工作内，选择利润尽可能大的工作来完成。

来确定贪的方向：因为每项工作的耗时都是一个单位时间，所以想获得尽可能多的利润，要选择尽可能多的工作。

但是，如果在选择m分钟过期的工作时，自己的1-m的时间都已经被工作填满了，该怎么办？

很容易想到暴力的算法：从自己已经选择的期限为1-m的工作中，找到一个工作利润最低的和当前备选工作比较，如果备选工作的利润高，就将两者替换。

这么做的复杂度为O(n^2),那么，有没有更优的解法？使用堆来维护贪心的选择，可以使复杂度达到O(nlogn)。

做法：

首先用优先队列建立堆，重载<运算符，使得两工作之间按利润进行排序。读入工作后，让它们按过期时间从低到高排序，可以想想为什么。

遍历工作数组，堆大小小于当前工作的过期时间，工作入堆，否则与堆顶比较，如果当前工作利润高，两者交换。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
int n;
struct node {
    int d, p;
    bool operator < (const node& x) const { return p > x.p; }
};
bool cmp(node d1, node d2) {
    if (d1.d == d2.d)return d1.p > d2.p;
    else return d1.d < d2.d;
}
node a[100010];
int main() {
    std::ios::sync_with_stdio(false);
    priority_queue< node >q;
    long long sum = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].d >> a[i].p;
    }
    sort(a + 1, a + 1 + n, cmp);
    for (int i = 1; i <= n; i++) {
        if (a[i].d <= q.size()) {
            if (a[i].p > q.top().p) {
                sum -= q.top().p;
                q.pop();
                sum += a[i].p;
                q.push(a[i]);
            }
        }
        else {
            sum += a[i].p;
            q.push(a[i]);
        }
    }
    cout << sum << endl;
    return 0;
}